不,你想多了,我并沒有發明.　　

---

　　動態樹?我會LCT!

　　然后加上在線和可持久化的前綴,這道題就變得面目可憎了起來.

　　對于一個森林,剛開始沒有邊.你需要維護下面的操作.

　　操作1:給定x,y,令x的父親為y.

　　操作2:給定t,x,k,求第t個版本中x的第k個祖先.如果沒有輸出0.

　　操作3:給定t,x,求第t個版本中x的深度.

　　20%:n<=100,m<=500,強制在線.

　　另外30%:不強制在線.

　　100%:n<=100000,m<=500000,有可能強制在線.　　

?

---

　　那么只說一下離線的好了.

　　這拿頭寫啊?看下面的題了.然后發現下面的題更難.于是回來想這道怎么做.

　　20分貌似很好拿.維護每個版本每個節點的父親,每個詢問就O(n)的往上跳就完事了.

　　然后開始剩下的70分怎么辦.想到了想LCT,但是可持久化解決不了.LCT一會拆開一會旋轉的,不好搞.我還會什么數據結構呢?我會樹鏈剖分!于是離線的30分就有了:先做出來最后的樹的樹鏈.用線段樹維護樹鏈區間的下標和最大時間戳.跑的時候,如果"版本號"<時間戳就不能過去,遞歸一個子區間即可.很穩的mlogn^2.

　　開始寫的時候,我想到,我只需要維護區間最大時間戳,為什么不寫遞增呢?

　　先全部讀入,用倍增的思想預處理出每個節點x的第2^k祖先fa[x][k]和這條路徑上的最大時間戳maxx[x][k].每次詢問就每次開開心心的跳就完事了.

using namespace std; int n; namespace _20 {int m,x,tx,ty,fa[110][500010],u,t,ans,op,k;int lastans; } namespace _30 {int m;struct ASK{int op,t,u,k;}o[500010];int t,tx,ty,k,u;int fa[100010][25],maxx[100010][25]; } int main() {freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);n=read();if(n<=100){using namespace _20;m=read();x=read();for(int i=1;i<=m;i++){for(int f=1;f<=n;f++)fa[f][i]=fa[f][i-1];op=(read()+lastans*x)%3;if(op==0){tx=(read()+lastans*x)%n+1;ty=(read()+lastans*x)%n+1;fa[tx][i]=ty;}else if(op==1){t=(read()+lastans*x)%m;u=(read()+lastans*x)%n+1;k=(read()+lastans*x)%n;while(fa[u][t]&&k){u=fa[u][t];k--;}if(k!=0)lastans=0;else lastans=u;write(lastans);}else{t=(read()+lastans*x)%m;u=(read()+lastans*x)%n+1;k=0;while(fa[u][t]){k++;u=fa[u][t];}lastans=k;write(k);}}return 0;}else {using namespace _30;m=read();t=read();for(int i=1;i<=m;i++){o[i].op=read()%3;if(o[i].op==0){tx=read()%n+1;ty=read()%n+1;fa[tx][0]=ty;maxx[tx][0]=i;}else if(o[i].op==1) {o[i].t=read()%m;o[i].u=read()%n+1;o[i].k=read()%n;}else {o[i].t=read()%m;o[i].u=read()%n+1;}} for(t=1;t<=20;t++){for(int i=1;i<=n;i++){fa[i][t]=fa[fa[i][t-1]][t-1];maxx[i][t]=max(maxx[i][t-1],maxx[fa[i][t-1]][t-1]);}}for(int i=1;i<=m;i++){hear:if(o[i].op==1){t=o[i].t;u=o[i].u;k=o[i].k;if(k==0){write(u);continue;}for(int f=20;f>=0;f--){if(k>=(1<<f)){if(maxx[u][f]>t){write(0);i++;if(i<=m)goto hear;else return 0;}u=fa[u][f];k-=(1<<f);}}write(u);}else if(o[i].op==2){t=o[i].t;u=o[i].u;k=0;for(int f=20;f>=0;f--){if(maxx[u][f]<=t&&fa[u][f]){u=fa[u][f];k+=(1<<f);}}write(k);}}return 0;} } 50分美滋滋

　　

?

轉載于:https://www.cnblogs.com/qywyt/p/10497154.html

總結

以上是生活随笔為你收集整理的离线可持久化动态树的全部內容，希望文章能夠幫你解決所遇到的問題。

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