洛谷T160512 G - 森林（并查集）

洛谷T160512 G - 森林（并查集）

题目思路：

按照正常的并查集思路来想的话，对于操作一 分裂成两颗树后，比较难维护的是其中一颗子树的所有子节点的祖先节点 因为 在find找祖先节点的时候会找到分裂前的的那个祖先节点，如果给每个子节点都更改的话，复杂度不允许

但是，如果我们把删边变为加边的话，这个并查集维护起来就比较方便了 ，我们从这颗树的最终状态向前操作

操作一 删边变为加边

操作二 值的变换，颠倒一下顺序（这里可以用栈记录一个节点的数值变化顺序）

Code：

int n,m,val[maxn],u[maxn],v[maxn],p[maxn],pre[maxn],ans[maxn],res;int s[maxn],vis[maxn],op[maxn],x[maxn],y[maxn];stackq[maxn];int find(int x) { if(x==p[x]) return x; return p[x] = find(p[x]);}void combine(int x,int y) { int dx = find(x); int dy = find(y); if(dx!=dy) p[dy] = dx,s[dx]+=s[dy];}int main() { n=read(),m=read(); for(int i=1 ; i<=n ; i++) { int x= read(); p[i]= i; q[i].push(x); } for(int i=1 ; i<=n-1 ; i++) u[i] =read(),v[i] = read(); for(int i=1 ; i<=m ; i++) { op[i]= read(); if(op[i]==1) x[i] =read(),vis[x[i]] = 1; else if(op[i]==2) x[i] =read(),y[i] =read(),q[x[i]].push(y[i]); else if(op[i]==3) x[i] =read(); } for(int i=1 ; i<=n ; i++) s[i] = val[i] = q[i]-(),q[i].pop(); for(int i=1 ; i<=n-1 ; i++) { if(vis[i]) continue; combine(u[i],v[i]); } for(int i=m ; i>=1 ; i--) { if(op[i]==1) { combine(u[x[i]],v[x[i]]); } else if(op[i]==2) { int temp = q[x[i]]-(); q[x[i]].pop(); int t = temp-val[x[i]] ; s[find(x[i])]+=t; val[x[i]] = temp; } else if(op[i]==3) ans[++res] = s[find(x[i])]; } dep(i,res,1) printf("%d\n",ans[i]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。