[spoj11414] combat on a tree 解题报告

本文主要是介绍[spoj11414] combat on a tree 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

拿来学了下线段树合并。
注意到当我们对线段树打反转标记，它节点的位置就改变了。那么我们线段树合并复杂度分析的那一套理论还适用么？答案是适用，因为我们可以认为所有节点都是打完所有标记以后的，就是不打标记合并，这样做的话它的合并其实是和打标记之前的合并是对称的，因为这棵树是一棵满二叉树。
代码：

#include<cstdio>
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<cmath>
const int N=1e5+5;
int a[N];
int next[N<<1],succ[N<<1],ptr[N],etot=1;
void addedge(int from,int to){next[etot]=ptr[from],ptr[from]=etot,succ[etot++]=to;
}void in(int &x){char c=getchar();while(c<'0'||c>'9')c=getchar();for(x=0;c>='0'&&c<='9';c=getchar())x=x*10+(c^'0');
}const int Log=17;
const int T=N*(Log+1);
int size[T],rev[T],ls[T],rs[T],root[N],ttot=1;
void build(int &node,int depth,int x){size[node=ttot++]=1;if(depth>=0)if(x>>depth&1)build(rs[node],depth-1,x);else build(ls[node],depth-1,x);
}
void paint(int node,int depth,int x){//printf("paint(%d,%d)\n",node,x);rev[node]^=x;if(depth>=0&&(x>>depth&1)){//puts("Swap");swap(ls[node],rs[node]);}
}
void pushdown(int node,int depth){if(rev[node]){paint(ls[node],depth-1,rev[node]),paint(rs[node],depth-1,rev[node]);rev[node]=0;}
}
void merge(int &u,int v,int depth,int x){if(!u||size[v]==1<<depth+1){u=v;//printf("Get v at [%d,%d):(%d,%d)\n",x,x+(1<<depth+1),size[u],size[v]);return;}if(!v||size[u]==1<<depth+1){//printf("Get u at [%d,%d):(%d,%d)\n",x,x+(1<<depth+1),size[u],size[v]);return;}//printf("merge(%d,%d,%d):(%d,%d)\n",u,v,depth,size[u],size[v]);pushdown(u,depth),pushdown(v,depth);merge(ls[u],ls[v],depth-1,x);merge(rs[u],rs[v],depth-1,x|1<<depth);size[u]=size[ls[u]]+size[rs[u]];//printf("size[%d]=%d\n",u,size[u]);
}
int query(int node){int ans=0;for(int depth=Log-1;depth>=0;--depth){pushdown(node,depth);ans<<=1;//printf("%d:%d(%d,%d)\n",depth,size[node],size[ls[node]],size[rs[node]]);if(size[ls[node]]==1<<depth){node=rs[node];ans|=1;//cout<<"Get:"<<(1<<depth)<<endl;}else node=ls[node];}return ans;
}int sg[N],q[N],fa[N],xors[N];
int ans[N];
int main(){freopen("bzoj_4134.in","r",stdin);freopen("bzoj_4134.out","w",stdout);int n;in(n);for(int i=1;i<=n;++i)in(a[i]);int u,v;for(int i=n;--i;){in(u),in(v);addedge(u,v),addedge(v,u);}q[0]=1;for(int h=0,t=1;h!=t;++h)for(int i=ptr[q[h]];i;i=next[i])if(succ[i]!=fa[q[h]]){q[t++]=succ[i];fa[succ[i]]=q[h];}for(int h=n;h--;){//printf("----%d----\n",q[h]);for(int i=ptr[q[h]];i;i=next[i])if(succ[i]!=fa[q[h]])xors[q[h]]^=sg[succ[i]];//printf("xors=%d\n",xors[q[h]]);if(!a[q[h]])build(root[q[h]],Log-1,xors[q[h]]);for(int i=ptr[q[h]];i;i=next[i])if(succ[i]!=fa[q[h]]){//printf("paint(%d,%d)\n",succ[i],xors[q[h]]^sg[succ[i]]);paint(root[succ[i]],Log-1,xors[q[h]]^sg[succ[i]]);merge(root[q[h]],root[succ[i]],Log-1,0);}sg[q[h]]=query(root[q[h]]);//printf("sg=%d\n",sg[q[h]]);}//for(int i=1;i<=n;++i)printf("sg[%d]=%d\n",i,sg[i]);if(sg[1]){for(int h=0;h<n;++h){if(!a[q[h]]&&!xors[q[h]])ans[++ans[0]]=q[h];for(int i=ptr[q[h]];i;i=next[i])if(succ[i]!=fa[q[h]])xors[succ[i]]^=xors[q[h]]^sg[succ[i]];}sort(ans+1,ans+ans[0]+1);for(int i=1;i<=ans[0];++i)printf("%d\n",ans[i]);}else puts("-1");
}