爱华网这里确实是用到了2115的一些思想，那题做法：http://blog.sina.com.cn/s/blog_6e63f59e0101bklw.html那道题求的是xor最大值，显然全部搞出来再高斯消元一下，枚举一遍就可以了。但是这道题求的是xor的种数，而且还删边，瞬间就傻掉了。首先转化一下，由于删边很难搞，就搞成加边。询问从后往前枚举，每次加一条边，这样的话比较容易判断，加进去是环边或者树边来更新。由2115得到启发，xor值是由链和环两部分构成的。于是和那道题一样，把环都搞到高斯消元的东西里面消成基数，链则另外存。两条链等价的条件就是它们用那些基数消出来的值一样。（大略想一想好像是这样但是具体的真心不太想得清楚囧）然后可以用一个set来维护这些值。如果当前基数表里面有A个元素，本质不同的链有B条，那么答案就是B * (1<< A) - 1，因为0是不能算进答案的。在加边的时候，如果判断加的这条边是树的边，那么dfs扩展当前的图；如果加边后形成了一个环，那么把环的xor值搞出来（具体和2115一样），再扔进高斯消元的里面消成基数。关于“扔进去再消”，之前做过bzoj3105，我是扔进去再全部消的，这样可以保证基数表是递减的（在消其他东西的时候只要按顺序枚举过去就可以了）；这次orz了标程发现可以不用扔一次全部消一次，只要把当前的w用当前的基数表消了以后记录一些东西，这样消其他东西的时候稍微麻烦一点，要两重循环，但是不需要每次扔一个进去全部消一次（具体我也没测试过，估计了一下速度应该是差不多的吧，这样看起来比较高贵）。然后具体怎么高斯消元以及set的一些小细节可以参考程序。#include<cstdio>
#include<cstring>
#include<set>
#include<iostream>
using namespace std;
#define LL longlong
#define N5050
#define M20200
struct edge{int y,next;LL w;}e[M <<1];
int can[M],dis[M],first[N],b[70],hei[70],vis[N];
int cnt,tot,n,m,q;
LL sum[N],ans[M],a[70],tmp[M];
set <LL> S;
void addedge(int x,int y,LL z){
e[cnt].next = first[x];e[cnt].y = y;e[cnt].w = z;first[x] = cnt ++;
e[cnt].next = first[y];e[cnt].y = x;e[cnt].w = z;first[y] = cnt ++;
}
LL gauss(LL w){
for (int i = 62;i >= 0;i --)if (b[i] &&((w >>i) & 1))
for (int j = 1;j <= tot;j ++) if (hei[j] == i) w ^= a[j];
return w;
}
void loop(LL w){
if (tot == 63) return;
w = gauss(w);
if (w == 0) return;
a[++ tot] = w;
int top,k = 0;
for (top = 62;!((w >>top) & 1);top --);
hei[tot] = top;
b[top] = 1;
set <LL> :: iterator j;
LL x;
for (j = S.begin();j != S.end();){
x= *j;
if ((x >>top) & 1){
tmp[++k] = x ^ w;
S.erase(j);
j= S.lower_bound(x);
}else j ++;
}
for(;k;k --) S.insert(tmp[k]);
}
void dfs(int x,int fa){
vis[x] = 1;
LL w = gauss(sum[x]);
S.insert(w);
int y;
for (int i = first[x];i != -1;i = e[i].next) if (!can[i / 2] &&e[i].y != fa){
y= e[i].y;
if (!vis[y]) sum[y] = sum[x] ^ e[i].w,dfs(y,x);
else loop(sum[y] ^ sum[x] ^ e[i].w);
}
}
int main(){
scanf("%d%d%d",&n,&m,&q);
int x,y;
LL z;
memset(first,-1,sizeof first);
for (int i = 0;i < m;i ++){
scanf("%d%d%lld",&x,&y,&z);
addedge(x,y,z);
}
for (int i = 1;i <= q;i ++) scanf("%d",&dis[i]),can[--dis[i]] = 1;
dfs(1,0);
ans[q + 1] = (1LL <<tot) * S.size() - 1;
for (int i = q;i;i --){
y= e[2 * dis[i]].y,x = e[2 * dis[i] + 1].y;
can[dis[i]] = 0;
if (vis[x] + vis[y] == 2) loop(sum[y] ^ sum[x] ^ e[2 * dis[i]].w);
else if (vis[x] &&!vis[y]) sum[y] = sum[x] ^ e[2 * dis[i]].w,dfs(y,x);
else if (!vis[x] &&vis[y]) sum[x] = sum[y] ^ e[2 * dis[i]].w,dfs(x,y);
ans[i] = (1LL <<tot) * S.size() - 1;
}
for (int i = 1;i <= q + 1;i ++) printf("%lldn",ans[i]);
return 0;
}
