我是靠谱客的博主 淡淡小鸽子,最近开发中收集的这篇文章主要介绍HDU5274 Dylans loves tree(树链剖分)很巧的点权更新Dylans loves tree,觉得挺不错的,现在分享给大家,希望可以做个参考。
概述
Dylans loves tree
Accepts: 49
Submissions: 262
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
问题描述
Dylans有一棵 N 个点的树。每个点有点权。树上节点标号为 1∼N 。 他得到了 Q 个询问,形式如下: ① 0 x y :把第 x 个点的点权修改为 y 。 ② 1 x y :对于 x∼y 路径上的每一种点权,是否都出现偶数次? 保证每次询问的路径上最多只有一种点权的出现次数是奇数次。 1≤N,Q≤100000 , 点权 A[i]∈N ,且都 ≤100000
输入描述
第一行一个正整数 T 表示数据组数( T≤3 且最多只有一组数据 N>1000 ) 第一行两个数 N、Q 表示树的点数和询问个数。 接下来 N−1 行每行一对数 (x,y) 表示树上的一条边。 接下来一行 N 个数表示每个点的点权。 接下来 Q 行每行三个数 (opt,x,y) 表示询问。
输出描述
对于每个②询问,如果全是偶数输出“-1",否则输出出现奇数次的权值。
输入样例
1 3 2 1 2 2 3 1 1 1 1 1 2 1 1 3
输出样例
-1 1
Hint
hack数据里N和Q必须小于等于10000,且对于读入的每一行末尾不应该有多余的空格。
解题:
#pragma comment(linker,"/STACK:1024000000,1024000000") #include<stdio.h> #include<iostream> #include<string.h> #include<map> using namespace std; const int N = 100005; #define LL __int64 struct EDG{ int to,next; }edg[N*2]; int eid,head[N]; int fath[N],deep[N],top[N],num[N],son[N],p[N],pos; void init(){ pos=0; eid=0; memset(head,-1,sizeof(head)); } void addEdg(int u,int v){ edg[eid].to=v; edg[eid].next=head[u]; head[u]=eid++; edg[eid].to=u; edg[eid].next=head[v]; head[v]=eid++; } void dfs(int u,int pre,int d){ fath[u]=pre; num[u]=1; deep[u]=d; son[u]=-1; for(int i=head[u]; i!=-1; i=edg[i].next){ int v=edg[i].to; if(v==pre)continue; dfs(v,u,d+1); num[u]+=num[v]; if(son[u]==-1||num[son[u]]<num[v]) son[u]=v; } } void getpos(int u,int root){ top[u]=root; p[u]=++pos; if(son[u]==-1) return ; getpos(son[u],root); for(int i=head[u]; i!=-1; i=edg[i].next){ int v=edg[i].to; if(son[u]==v||v==fath[u]) continue; getpos(v,v); } } int root[N*3]; //记录当前区间内所有值的xor int a[N]; void build(int l,int r,int k){ if(l==r){ root[k]=a[l]; return ; } int m=(l+r)>>1; build(l,m,k<<1); build(m+1,r,k<<1|1); root[k]=root[k<<1]^root[k<<1|1]; } void updata(int l,int r,int k,int id,int vule){ if(l==r){ root[k]=vule; return ; } int m=(l+r)>>1; if(id<=m) updata(l,m,k<<1,id,vule); else updata(m+1,r,k<<1|1,id,vule); root[k]=root[k<<1]^root[k<<1|1]; } int query(int l,int r,int k,int L,int R){ if(L<=l&&r<=R){ return root[k]; } int m=(l+r)>>1 , ans=0; if(L<=m) ans^= query(l,m,k<<1,L,R); if(m<R) ans^=query(m+1,r,k<<1|1,L,R); return ans; } void swp(int &aa,int &bb){ int tt=aa; aa=bb; bb=tt; } int Operat(int u,int v){ int fu=top[u] , fv=top[v],ans=0; while(fu!=fv){ if(deep[fu]<deep[fv]){ swp(fu,fv); swp(u,v); } ans^= query(1,pos,1,p[fu],p[u]); u=fath[fu]; fu=top[u]; } if(deep[u]>deep[v]) swp(u,v); ans^=query(1,pos,1,p[u],p[v]); return ans; } int main() { int T,n,q,val[N],u,v; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&q); init(); for(int i=1; i<n; i++) { scanf("%d%d",&u,&v); addEdg(u,v); } for(int i=1; i<=n; i++){ scanf("%d",&val[i]); val[i]++; } dfs(1,1,1); getpos(1,1); for(int i=1; i<=n; i++) a[p[i]]=val[i]; build(1,pos,1); while(q--){ int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==0) updata(1,pos,1,p[x],y+1);//加1 else{ printf("%dn",Operat(x,y)-1);//减1 } } } return 0; }
最后
以上就是淡淡小鸽子为你收集整理的HDU5274 Dylans loves tree(树链剖分)很巧的点权更新Dylans loves tree的全部内容,希望文章能够帮你解决HDU5274 Dylans loves tree(树链剖分)很巧的点权更新Dylans loves tree所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复