bzoj2322 梦想封印

题意和题解见思路索引。

标程及易错点：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll read()

 {

     ll x=;char ch=getchar();

     while (ch<''||ch>'') ch=getchar();

     while (''<=ch&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();

     return x;

 }

 const int M=;

 const int N=;

 set<ll> s;

 int cnt,head[N],blo,u[M],v[M],top,x,y,pos,vis[N],tag[M*],n,m,Q,e[M];

 ll ans[M],ww,w[N],base[],q[N];

 set<ll>::iterator it;

 struct node{int to,next;ll w;}num[M*];

 void add(int x,int y,ll w)

 {num[++cnt].to=y;num[cnt].next=head[x];num[cnt].w=w;head[x]=cnt;}

 void ins(ll x)

 {

     if (!x) return;

     for (int i=;i>=;i--)//从大到小

       if ((x>>i)&) {base[i]=x;blo++;break;}

     for (top=,it=s.begin();it!=s.end();++it) q[++top]=min(*it,*it^x);

     s.clear();

     for (int j=;j<=top;j++) s.insert(q[j]);

 }

 ll match(ll x)

 {

     for (int i=;i>=&&x;i--)//从高位到低位消

       if ((x^base[i])<x) x^=base[i];//能消的位都消元

     return x;

 }

 void dfs(int x,int fa)

 {

    vis[x]=;s.insert(match(w[x]));

    for (int i=head[x];i;i=num[i].next)

      if (num[i].to!=fa&&!tag[i])

      {

         if (!vis[num[i].to]) w[num[i].to]=w[x]^num[i].w,dfs(num[i].to,x);

         else ins(match(w[x]^w[num[i].to]^num[i].w));//这里加环也要对set消元

      }

 }

 int main()

 {

     n=read();m=read();Q=read();

     for (int i=;i<=m;i++) u[i]=read(),v[i]=read(),ww=read(),add(u[i],v[i],ww),add(v[i],u[i],ww);

     for (int i=;i<=Q;i++) e[i]=read(),tag[e[i]*-]=tag[e[i]*]=;

     dfs(,-);

     ans[Q+]=(ll)s.size()*(1ll<<blo)-;

     for (int i=Q;i>=;i--)

     {

         tag[e[i]*-]=tag[e[i]*]=;

         x=u[e[i]],y=v[e[i]],ww=num[e[i]*].w;

         if (vis[x]&&vis[y]) ins(match(w[x]^w[y]^ww));

         else if (vis[x]) w[y]=w[x]^ww,dfs(y,x);

         else if (vis[y]) w[x]=w[y]^ww,dfs(x,y);

         ans[i]=(ll)s.size()*(1ll<<blo)-;

     }

     for (int i=;i<=Q+;i++) printf("%lld\n",ans[i]);

     return ;

 }