题目大意：给定一张带权无向图，每次删去一条边并询问从点1出发走一条路径可以走出多少种不同的边权异或和
?
删边不好做 首先倒着做 把删边改成加边
?
回忆2115那题的做法 我们可以把一条路径的异或和拆成一条简单路径和一些环的异或值
2115是求最大异或和 这个题是求异或和的个数
因此我们维护两个集合 环的异或和集合和路径的异或和集合
?
这里说的路径包括原地不动 即从1到1的路径
如果一个环的异或和能被其它环线性表示 那么这个环对答案显然没有贡献 于是这个环就可以从集合中删掉
因此环的集合要维护一个线性基的形式
?
如果一条路径的异或和异或上一些环之后等于另一条路径，这条路径对答案显然没有贡献
因此路径的集合需要对线性基消元，且保证消元后不重
?
设环的集合大小为R，路径的集合大小为P，那么答案就是P*2^R-1
?
不过这题需要动态维护- - 实现起来就比较麻烦了- - 我细说吧- -
?
首先思想是维护一棵以1为根的生成树，将树上的路径都视作路径，每条非树边对应一个环
?
路径集合的去重利用set来完成
?
每添加一条边，步骤如下：
?
如果边的两端点都被访问过，就把这条边所在环的异或值扔进线性基中消元
如果此次消元后线性基被更新，那么将set中所有的路径取出，对本次更新的线性基消元后再放回去
?
如果只有一端点被访问过，那么就深搜另一端点所在联通块，标记访问节点
对于深搜到的每个点，将1号节点到该节点的路径的异或和对线性基消元后扔进set
对于深搜到的每条非树边，扔进线性基中消元并更新set中的元素
?
时间复杂度O(nlognlogk) 其中k是最大的边权
?
?
#include
#include
#include
#include
#include
#define M 20200 using namespace std; struct edge{ int x,y; long long z; }edges[M]; struct abcd{ int to,next; long long f; }table[M<<1]; int head[M],tot=1; int n,m,q,cnt; bool _v[M],v[M]; int queries[M]; long long a[M],ans[M],linear_bases[64]; set
s; void Add(int x,int y,long long z) { table[++tot].to=y; table[tot].f=z; table[tot].next=head[x]; head[x]=tot; } void Gauss_Elimination(long long x) { int i; for(i=62;~i;i--) if( (x^linear_bases[i])
::iterator it; for(it=s.begin();it!=s.end();it++) stack[++top]=*it; for(s.clear();top;top--) s.insert( min(stack[top],stack[top]^x) ); } void DFS(int x,int from) { int i; v[x]=1; a[x]=a[table[from^1].to]^table[from].f; long long temp=a[x]; for(i=62;~i;i--) temp=min(temp,temp^linear_bases[i]); s.insert(temp); for(i=head[x];i;i=table[i].next) if(i^from^1) { if(!v[table[i].to]) DFS(table[i].to,i); else Gauss_Elimination(table[i].f^a[x]^a[table[i].to]); } } void Insert(int id) { int x=edges[id].x; int y=edges[id].y; Add(x,y,edges[id].z); Add(y,x,edges[id].z); if(v[x]&&v[y])www.2cto.com Gauss_Elimination(edges[id].z^a[x]^a[y]); else if(v[x]) DFS(y,tot-1); else if(v[y]) DFS(x,tot); } int main() { int i,x,y; long long z; cin>>n>>m>>q; for(i=1;i<=m;i++) { #ifdef ONLINE_JUDGE scanf("%d%d%lld",&x,&y,&z); #else scanf("%d%d%I64d",&x,&y,&z); #endif edges[i].x=x; edges[i].y=y; edges[i].z=z; } for(i=1;i<=q;i++) { scanf("%d",&queries[i]); _v[queries[i]]=true; } s.insert(0); v[1]=1; for(i=1;i<=m;i++) if(!_v[i]) Insert(i); for(i=q;i;i--) { ans[i]=s.size()*(1ll<
?