看起來像是并查集，但是是拆集合，考慮時間倒流，先把標記都打上，然后把并查集做出來
每次到一個修改點就把這個點的計數(shù)s[u]--，當這個s為0時就把這個點和他的父親合并（因為可能有多次標記）

#include<iostream> #include<cstdio> using namespace std; const int N=100005; int n,q,h[N],cnt,s[N],a[N],f[N],fa[N],ans[N],tot; char c[N][5]; struct qwe {int ne,to; }e[N<<1]; int read() {int r=0,f=1;char p=getchar();while(p>'9'||p<'0'){if(p=='-')f=-1;p=getchar();}while(p>='0'&&p<='9'){r=r*10+p-48;p=getchar();}return r*f; } void add(int u,int v) {cnt++;e[cnt].ne=h[u];e[cnt].to=v;h[u]=cnt; } int zhao(int x) {return f[x]==x?x:f[x]=zhao(f[x]); } void dfs(int u,int fat) {fa[u]=fat;if(!s[u])f[zhao(u)]=zhao(fat);for(int i=h[u];i;i=e[i].ne)if(e[i].to!=fat)dfs(e[i].to,u); } int main() {n=read(),q=read();for(int i=1;i<n;i++){int x=read(),y=read();add(x,y),add(y,x);}s[1]=1;for(int i=1;i<=q;i++){scanf("%s",c[i]);a[i]=read();if(c[i][0]=='C')s[a[i]]++;}for(int i=1;i<=n;i++)f[i]=i;dfs(1,1);for(int i=q;i>=1;i--){if(c[i][0]=='C'){s[a[i]]--;if(!s[a[i]])f[zhao(a[i])]=zhao(fa[a[i]]);}elseans[++tot]=zhao(a[i]);}for(int i=tot;i>=1;i--)printf("%d\n",ans[i]);return 0; }

轉載于:https://www.cnblogs.com/lokiii/p/9719074.html

總結

以上是生活随笔為你收集整理的bzoj 4551: [Tjoi2016Heoi2016]树【并查集】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。