正題

題目鏈接:https://www.luogu.com.cn/problem/CF1137F

---

題目大意

給出$n$個點的一棵樹，第$i$個點權值為$i$。

一棵樹的刪除序列定義為每次刪除編號最小的葉子并將其加入序列末尾。

要求支持

修改一個點的權值為一個比目前所有權值都要大的一個值

詢問一個點在刪除序列的位置

詢問兩個點在刪除序列的先后順序

$1\le n,q\le 2\times 10^5$

---

解題思路

假設我們已經確定的先后順序，目前最大的權值為$y$號點，然后修改一個點$x$時相當于把$y～x$的路徑上所有點依次放在序列末尾。

相當于我們要支持提出一條樹鏈，可以考慮用$LCT$實現(xiàn)。

以權值最大的點為根，我們對于每一條樹鏈（splay）附上同一個顏色，那么一個點的答案就是顏色編號比它小的點數(shù)+所在樹鏈上深度比它小的點數(shù)+1。

然后修改就相當于連接+換根+換顏色。顏色方面可以用樹狀數(shù)組維護前綴和，然后再$Access$的時候進行修改，換根也是可以用$LCT$做到的。

時間復雜度$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #define lowbit(x) (x&-x) using namespace std; const int N=2e5+10; struct node{int to,next; }a[N<<1]; int n,q,cnt,tot,ls[N],col[N]; struct BinaryInTree{int t[N<<1],n;void Change(int x,int val){while(x<=n){t[x]+=val;x+=lowbit(x);}return;}int Ask(int x){int ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans;} }B; struct LCT{int fa[N],t[N][2],siz[N];bool r[N];stack<int> s;bool Nroot(int x){return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);}bool Direct(int x){return t[fa[x]][1]==x;}void PushUp(int x){siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return;}void Rev(int x){r[x]^=1;swap(t[x][0],t[x][1]);return;}void PushDown(int x){if(t[x][0])col[t[x][0]]=col[x];if(t[x][1])col[t[x][1]]=col[x];if(!r[x])return;Rev(t[x][0]);Rev(t[x][1]);r[x]=0;return;}void Rotate(int x){int y=fa[x],z=fa[y];int xs=Direct(x),ys=Direct(y);int w=t[x][xs^1];if(Nroot(y))t[z][ys]=x;t[y][xs]=w;t[x][xs^1]=y;if(w)fa[w]=y;fa[y]=x;fa[x]=z;PushUp(y);PushUp(x);return;}void Splay(int x){int y=x;s.push(x);while(Nroot(y))y=fa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){int y=fa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)==Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(int x){for(int y=0;x;y=x,x=fa[x]){Splay(x);t[x][1]=0;PushUp(x);B.Change(col[x],-siz[x]);B.Change(cnt,siz[x]);t[x][1]=y;PushUp(x);}return;}void MakeRoot(int x){++cnt;Access(x);Splay(x);col[x]=cnt;Rev(x);return;}int Ask(int x){Splay(x);return siz[t[x][1]]+1+B.Ask(col[x]-1);} }T; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){col[x]=x;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==T.fa[x])continue;T.fa[y]=x;dfs(y);if(col[y]>col[x]){col[x]=col[y];T.t[x][1]=y;}}B.Change(col[x],1);T.PushUp(x); } int main() {scanf("%d%d",&n,&q);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}B.n=n+q;cnt=n;dfs(n);for(int i=1;i<=q;i++){char op[6];int x,y;scanf("%s%d",op,&x);if(op[0]=='u')T.MakeRoot(x);else if(op[0]=='w')printf("%d\n",T.Ask(x));else if(op[0]=='c'){scanf("%d",&y);int l=T.Ask(x),r=T.Ask(y);if(l<r)printf("%d\n",x);else printf("%d\n",y);}}return 0; }

總結

以上是生活随笔為你收集整理的CF1137F-Matches Are Not a Child‘s Play【LCT】的全部內容，希望文章能夠幫你解決所遇到的問題。

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