首页 > 代码库 > AC日记——Dylans loves tree hdu 5274
AC日记——Dylans loves tree hdu 5274
Dylans loves tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1611 Accepted Submission(s): 388
Problem Description
Dylans is given a tree with N
nodes.
All nodes have a value A[i].Nodes on tree is numbered by 1∼N.
Then he is given Q questions like that:
①0 x y：change node x′s value to y
②1 x y：For all the value in the path from x to y,do they all appear even times?
For each ② question,it guarantees that there is at most one value that appears odd times on the path.
1≤N,Q≤100000, the value A[i]∈N and A[i]≤100000
All nodes have a value A[i]
Then he is given Q
①0 x y
②1 x y
For each ② question,it guarantees that there is at most one value that appears odd times on the path.
1≤N,Q≤100000
Input
In the first line there is a test number T.
(T≤3 and there is at most one testcase that N>1000)
For each testcase:
In the first line there are two numbers N and Q.
Then in the next N−1 lines there are pairs of (X,Y) that stand for a road from x to y.
Then in the next line there are N numbers A1..AN stand for value.
In the next Q lines there are three numbers(opt,x,y).
(T≤3
For each testcase:
In the first line there are two numbers N
Then in the next N−1
Then in the next line there are N
In the next Q
Output
For each question ② in each testcase,if the value all appear even times output "-1",otherwise output the value that appears odd times.
Sample Input
13 21 22 31 1 11 1 21 1 3
Sample Output
-11
Hint
If you want to hack someone,N and Q in your testdata must smaller than 10000，and you shouldn‘t print any space in each end of the line.
Source
BestCoder Round #45
思路：
判断树上路径是否有出现过奇数次的权值；
数据保证一条路径上最多一个出现奇数次的权值；
因为x^x=0,0^x=x的性质；
我们可以用异或和；
把一条路径的全部权值都异或；
如果等于0则不存在，否则就输出；
同时，因为0^0=0；
所以我们全部的权值都+1；
然后，输出时再-1；
来，上代码：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define maxn 100005using namespace std;struct TreeNodeType { int l,r,dis,mid;};struct TreeNodeType tree[maxn<<2];struct EdgeType { int v,next;};struct EdgeType edge[maxn<<1];int if_z,t,n,q,dis[maxn],dis_[maxn];int cnt=0,head[maxn],deep[maxn],f[maxn];int top[maxn],size[maxn],flag[maxn];char Cget;inline void in(int &now){ now=0,if_z=1,Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) { if(Cget==‘-‘) if_z=-1; Cget=getchar(); } while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); } now*=if_z;}inline void edge_add(int u,int v){ cnt++; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt;}void search_1(int now,int fa){ int pos=cnt++; deep[now]=deep[fa]+1,f[now]=fa; for(int i=head[now];i;i=edge[i].next) { if(edge[i].v==fa) continue; search_1(edge[i].v,now); } size[now]=cnt-pos;}void search_2(int now,int chain){ top[now]=chain,flag[now]=++cnt; dis[flag[now]]=dis_[now]+1; int pos=0; for(int i=head[now];i;i=edge[i].next) { if(edge[i].v==f[now]) continue; if(size[edge[i].v]>size[pos]) pos=edge[i].v; } if(pos==0) return ; search_2(pos,chain); for(int i=head[now];i;i=edge[i].next) { if(edge[i].v==pos||edge[i].v==f[now]) continue; search_2(edge[i].v,edge[i].v); }}inline void tree_up(int now){ tree[now].dis=tree[now<<1].dis^tree[now<<1|1].dis;}void tree_build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].dis=dis[l]; return ; } tree[now].mid=(l+r)>>1; tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); tree_up(now);}void tree_change(int now,int to,int x){ if(tree[now].l==tree[now].r) { tree[now].dis=x; return ; } if(to<=tree[now].mid) tree_change(now<<1,to,x); else tree_change(now<<1|1,to,x); tree_up(now);}int tree_query(int now,int l,int r){ if(tree[now].l==l&&tree[now].r==r) { return tree[now].dis; } if(l>tree[now].mid) return tree_query(now<<1|1,l,r); else if(r<=tree[now].mid) return tree_query(now<<1,l,r); else return tree_query(now<<1,l,tree[now].mid)^tree_query(now<<1|1,tree[now].mid+1,r);}int solve_do(int x,int y){ int pos=0; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); pos=pos^tree_query(1,flag[top[x]],flag[x]); x=f[top[x]]; } if(deep[x]>deep[y]) swap(x,y); pos=pos^tree_query(1,flag[x],flag[y]); if(pos==0) return -1; else return pos-1;}int main(){ in(t); int lit=t; while(t--) { memset(head,0,sizeof(head)); in(n),in(q);cnt=0;int u,v; for(int i=1;i<n;i++) { in(u),in(v); edge_add(u,v); edge_add(v,u); } for(int i=1;i<=n;i++) in(dis_[i]); cnt=0,search_1(1,0); cnt=0,search_2(1,1); tree_build(1,1,n); int type; for(int i=1;i<=q;i++) { in(type),in(u),in(v); if(type) printf("%d\n",solve_do(u,v)); else tree_change(1,u,v+1); } } return 0;}
AC日记——Dylans loves tree hdu 5274
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。