HDU 5274 Dylans loves tree(树链剖分)
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5274
【题目大意】
给出一棵树,每个点有一个权值,权值可修改,且大于等于0,询问链上出现次数为奇数的数,题目保证每次询问的链上最多只有一个数出现次数为奇数。如果不存在这样的数,就输出-1。
【题解】
题目等价于求链上点的异或和,树链剖分,线段树维护区间异或和,然后链上查询即可,注意到存在权值为0的特殊情况,所以我们将更新的数字都+1,在最后处理答案的时候-1即可。
【代码】
#include <cstdio> #include <algorithm> #include <climits> #include <cstring> using namespace std; const int N=300010; int val[N],tot,op,x,d[N],num[N],ed=0,u,w,n,m,i,v[N],vis[N],f[N],g[N],nxt[N],size[N],son[N],st[N],en[N],dfn,top[N],t;char ch; void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;} void dfs(int x){ size[x]=1; for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){ f[v[i]]=x,d[v[i]]=d[x]+1; dfs(v[i]),size[x]+=size[v[i]]; if(size[v[i]]>size[son[x]])son[x]=v[i]; } } void dfs2(int x,int y){ if(x==-1)return; st[x]=++dfn;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]); en[x]=dfn; } struct Node{int l,r;int sum;}T[N*4]; void build(int x,int l,int r){ T[x].l=l;T[x].r=r;T[x].sum=0; if(l==r)return;int mid=(l+r)>>1; build(x<<1,l,mid);build((x<<1)|1,mid+1,r); } void up(int x){T[x].sum=T[x<<1].sum^T[x<<1|1].sum;} void update(int x,int k,int val){ if(T[x].l==k&&T[x].r==k){T[x].sum^=val;return;} int mid=(T[x].l+T[x].r)>>1; if(k<=mid)update(x<<1,k,val); else update((x<<1)|1,k,val); up(x); } int sum(int x,int l,int r){ if(l<=T[x].l&&T[x].r<=r)return T[x].sum; int mid=(T[x].l+T[x].r)>>1,tmp=0; if(l<=mid)tmp^=sum(x<<1,l,r); if(r>mid)tmp^=sum((x<<1)|1,l,r); return tmp; } int chain(int x,int y){ int res=0; for(;top[x]!=top[y];x=f[top[x]]){ if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;} res^=sum(1,st[top[x]],st[x]); }if(d[x]<d[y]){int z=x;x=y;y=z;} res^=sum(1,st[y],st[x]); return res; } void init(){ memset(g,dfn=ed=tot=0,sizeof(g)); memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt)); memset(son,-1,sizeof(son)); } int cas; int main(){ scanf("%d",&cas); while(cas--){ init(); scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ scanf("%d%d",&u,&w); add(u,w); add(w,u); }dfs(1);dfs2(1,1); build(1,1,dfn); for(int i=1;i<=n;i++){ scanf("%d",&val[i]); val[i]++; update(1,st[i],val[i]); } while(m--){ scanf("%d%d%d",&op,&u,&w); if(op){ printf("%d\n",chain(u,w)-1); }else{ update(1,st[u],val[u]^(w+1)); val[u]=w+1; } } }return 0; }
2020年1月21日 15:35
'One of the oldest traditional markets in Lancashire'
Open 4 days a week, all year round. minibus hire sheffield cheap minibus hire thorpe park minibus hire Cheap Minibus Coach Hire minibus hire kent coach hire peterborough minibus hire glasgow minibus hire blackpool minibus hire scarborough minibus hire with driver minibus hire cardiff minibus hire barnsley minibus hire wolverhampton Cheap Minibus Coach Hire