好吧，洛谷的數據比較水暴力就可以過。。。。（而且跑到飛快）

不過（BZ水不過去）還是講講正規的做法。

其實一眼可以看出可以樹剖，但是，碼起來有點麻煩。

其實有一種更簡單的離線做法。

我們很容易聯想到并查集，利用并查集來維護各個點的最近的標記的祖先，但是加入標記后會產生分離的操作，這對并查集來說不好操作

所以我們先將所有的詢問讀入，將所有的標記都打上去。

從后往前處理。如果有一個點的標記變為了0，就將該點與它的父親合并。

不知為何，在luogu上跑的比暴力要慢一點。。。。

# include<iostream> # include<cstdio> # include<cmath> # include<cstring> # include<algorithm> using namespace std; const int mn = 100005; int n,m; int c[mn],a[mn],fa[mn],ans[mn]; char opt[mn]; struct edge{int next,to;}e[mn*2]; int head[mn],edge_max; inline void add_edge(int x,int y) {e[++edge_max]=(edge){head[x],y};head[x]=edge_max; } int f[mn];//并查集的fa數組 int find(int x) {return f[x]==x?x:f[x]=find(f[x]); } void dfs(int x) {f[x]=c[x]?x:fa[x];for(int i=head[x];i;i=e[i].next){int y=e[i].to;if (y!=fa[x]) fa[y]=x,dfs(y);} } int main() {int x,y;scanf("%d%d",&n,&m);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add_edge(x,y);add_edge(y,x);}c[1]=1;for(int i=1;i<=m;i++){scanf(" %c%d",&opt[i],&a[i]);if (opt[i]=='C') c[a[i]]++;}dfs(1);for(int i=m;i>=1;i--){if (opt[i]=='C'){c[a[i]]--;if(!c[a[i]])f[a[i]]=fa[a[i]];}else ans[i]=find(a[i]);}for(int i=1;i<=m;i++){if(ans[i])printf("%d\n",ans[i]);}return 0; }

　　

轉載于:https://www.cnblogs.com/logeadd/p/8685974.html

總結

以上是生活随笔為你收集整理的BZOJ 4551树题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。