題目：https://www.luogu.org/problemnew/show/P4092

也考慮過離線。但沒有想到倒序會(huì)很方便。

題解：考慮記錄每個(gè)點(diǎn)的最近標(biāo)記祖先。

　　　對(duì)于離標(biāo)記點(diǎn)很遠(yuǎn)的點(diǎn)，豈不是要慢慢找過去？

　　　所以想到可以路徑壓縮的并查集。

　　　并查集在此題中的特點(diǎn)是刪點(diǎn)很容易，刪x就是把fa[x]=x改成fa[x]=(x的直接父親)，所以可以倒序離線！

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=100005; int n,q,fa[N],cz[N],ans[N],ff[N],cnt[N],ct; bool b[N]; int find(int a) {if(fa[a]==a)return a;return fa[a]=find(fa[a]); } int main() {scanf("%d%d",&n,&q);int x,y;char ch;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);ff[y]=x;}for(int i=1;i<=q;i++){scanf(" %c%d",&ch,&x);cz[i]=x;b[i]=(ch=='C');if(b[i])fa[x]=x,cnt[x]++;}fa[1]=1;ff[1]=1;for(int i=2;i<=n;i++)if(!fa[i])fa[i]=ff[i];for(int i=q;i;i--){int k=cz[i];if(b[i]&&!--cnt[k])fa[k]=ff[k];if(!b[i])ans[++ct]=find(k);}for(int i=ct;i;i--)printf("%d\n",ans[i]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Narh/p/8763497.html

總結(jié)

以上是生活随笔為你收集整理的洛谷4092 树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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