题目大意

给你一棵树，接下来对这棵树进行三种操作：

1、询问两点之间的距离。

2、让某个点变为它原来的第\(h\)个祖先的最后一个儿子。

3、求\(dfs\)序中最后一个深度为\(k\)的点。

---

正解

第一种是Cold_Chair大爷提出来的\(LCT\)维护\(ETT\)的做法。

具体怎样就不说了……据说代码5000+

第二种就直接是\(ETT\)了（其实这是一道ETT的板题啊）

对于入栈点（记作\(l\)）打个\(+1\)，对于出栈点（记作\(r\)）打个\(-1\)，维护前缀和。这个前缀和相当于深度。

这里维护前缀和的方法比较巧妙，不需要区间修改，具体见程序。

对于第一个操作，找到\(l_u\)和\(l_v\)之间最小的深度。显然这个深度就是它们的\(LCA\)的深度。

对于第二个操作，找第\(h\)个祖先的时候先求出祖先的深度，然后在前面找最靠右的深度为它的点。显然前缀和是连续的，所以可以在\(splay\)上二分。如果它是入栈点，就是要找的那个祖先；如果是出栈点，那它的父亲就是那个祖先。

对于第三个操作，直接找最后面前缀和为\(k\)的点。和操作二一样。

---

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define N 100010#define INF 1000000000int n,m;vector
           
             to[N];struct Node *null,*root;struct Node{ Node *fa,*c[2]; int val,sum,mx,mn; inline void init(int _val){ fa=c[0]=c[1]=null; val=sum=mx=mn=_val; } inline void update(){ sum=c[0]->sum+c[1]->sum+val; mx=max(max(c[0]->mx,c[0]->sum+val+c[1]->mx),c[0]->sum+val); mn=min(min(c[0]->mn,c[0]->sum+val+c[1]->mn),c[0]->sum+val); } inline bool getson(){return fa->c[0]!=this;} inline void rotate(){ Node *y=fa,*z=y->fa; if (z!=null) z->c[y->getson()]=this; bool k=getson(); fa=z; y->c[k]=c[k^1],c[k^1]->fa=y; c[k^1]=y,y->fa=this; sum=y->sum,mx=y->mx,mn=y->mn; y->update(); } inline void splay(Node *t){ while (fa!=t){ if (fa->fa!=t) getson()!=fa->getson()?rotate():fa->rotate(); rotate(); } if (t==null) root=this; }} in[N],out[N],*beg,*end;inline Node *nxt(Node *t,bool dir){ t->splay(null); Node *res=t->c[dir]; for (;res->c[dir^1]!=null;res=res->c[dir^1]); return res;}inline void push_back(Node *x){ Node *t=root; for (;t->c[1]!=null;t=t->c[1]); t->splay(null); t->c[1]=x,x->fa=t; t->update();}inline Node *split(Node *l,Node *r){ l=nxt(l,0),r=nxt(r,1); r->splay(null),l->splay(r); Node *t=l->c[1]; l->c[1]=null,t->fa=null; l->update(),r->update(); return t;}inline void insert(Node *t,Node *p){ p->splay(null); Node *pre=nxt(p,0); pre->splay(p); pre->c[1]=t,t->fa=pre; pre->update(),p->update();}inline Node *find_last(Node *t,int k){ t->splay(null); Node *x=t->c[0],*res=null; while (1){ if (x->c[1]!=null && x->c[1]->mn<=k-x->c[0]->sum-x->val && k-x->c[0]->sum-x->val<=x->c[1]->mx){ k-=x->c[0]->sum+x->val; x=x->c[1]; continue; } else if (x->c[0]->sum+x->val==k) return x; x=x->c[0]; } return res;}void dfs(int x){ in[x].init(1); push_back(&in[x]); for (int i=0;i
            
             init(0),root=beg; dfs(1); end=new Node,end->init(0),push_back(end); for (int i=1;i<=m;++i){ int op; scanf("%d",&op); if (op==1){ int u,v,depu,depv,deplca; scanf("%d%d",&u,&v); if (u==v){ printf("0\n"); continue; } in[u].splay(null),in[v].splay(&in[u]); if (in[v].getson()==0) swap(u,v); Node *l=nxt(&in[u],0),*r=nxt(&in[v],1); r->splay(null),l->splay(r); deplca=l->c[0]->sum+l->val+l->c[1]->mn; depu=l->c[0]->sum+l->val+1; depv=l->sum; printf("%d\n",depu+depv-deplca*2); } else if (op==2){ int v,h,anc; scanf("%d%d",&v,&h); in[v].splay(null); Node *tmp=find_last(&in[v],in[v].c[0]->sum+1-h); fa[v]=anc=(tmp->val==-1?fa[tmp-out]:tmp-in); Node *t=split(&in[v],&out[v]); insert(t,&out[anc]); } else{ int k; scanf("%d",&k); Node *tmp=find_last(end,k+1); printf("%d\n",tmp->val==-1?fa[tmp-out]:tmp-in); } } return 0;}
            
           
          
         
        
       
      
     
    

---

总结

\(LCT\)搞不了的东西，要试试\(ETT\)。