题目大意

给你一棵树，然后有一堆询问，每次给出两个点。

问所有点到两个点中最近点的距离的最大值。

---

正解

本来打了倍增，然后爆了，也懒得调……

显然可以在两个点之间的路径的中点处割开，一边归一个点管。

有个比较显然的思路是DP，设\(f_x\)表示\(x\)子树内的最远点，\(g_x\)向父亲那边走的最远点。

然后就可以倍增搞，合并一下……

代码复杂度极高。

然后有个简单又自然的思路是直接打\(LCT\)。直接把中间那条边断掉，然后求最远点即可。

想法倒是简单自然，接下来的问题就是，如何求最远点？

每条链可以维护子树到链顶的距离。设最远距离为\(len\)，则合并的时候，就是左区间的\(len\)、右区间的\(len\)加上左区间的\(siz\)加\(1\)、中间的答案（包括虚边转移过来的）加左区间的\(siz\)。这三个东西取最大值。

至于虚边信息，由于维护的是最大值，不能像和一样加加减减，所以要用multiset维护（或者手写数据结构也可以哈）。

然后你就会发现一个bug——翻转的时候怎么办？

\(len\)的计算是不满足交换律的，所以我们要维护一个\(len2\)，表示\(len\)反过来的样子。合并的时候跟上面相反就是了。换句话来说，就是在重链管的整棵子树中，到达链底的最远距离。

翻转的时候直接将两个交换就行了。

---

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 100010#define INF 1000000000int n,m;struct Node{    Node *fa,*c[2];    bool is_root,rev;    int siz,len1,len2,mx;    multiset
        
          s;    inline void reverse(){        swap(c[0],c[1]);        swap(len1,len2);        rev^=1;    }    inline void pushdown(){        if (rev){            c[0]->reverse();            c[1]->reverse();            rev=0;        }    }    void push(){        if (!is_root)            fa->push();        pushdown();    }    inline void update(){        siz=c[0]->siz+c[1]->siz+1;        len1=max(max(c[0]->len1,c[0]->siz+1+c[1]->len1),c[0]->siz+mx+1);        len2=max(max(c[1]->len2,c[1]->siz+1+c[0]->len2),c[1]->siz+mx+1);    }    inline bool getson(){return fa->c[0]!=this;}    inline void rotate(){        Node *y=fa,*z=y->fa;        if (y->is_root){            is_root=1;            y->is_root=0;        }        else            z->c[y->getson()]=this;        int k=getson();        fa=z;        y->c[k]=c[k^1],c[k^1]->fa=y;        c[k^1]=y,y->fa=this;        siz=y->siz,len1=y->len1,len2=y->len2;        y->update();    }    inline void splay(){        push();        while (!is_root){            if (!fa->is_root){                if (getson()!=fa->getson())                    rotate();                else                    fa->rotate();            }            rotate();        }    }} d[N],*null=d;inline Node *access(Node *x){    Node *y=null;    for (;x!=null;y=x,x=x->fa){        x->splay();        if (x->c[1]!=null){            x->s.insert(x->c[1]->len1);            x->mx=max(x->mx,x->c[1]->len1);        }        x->c[1]->is_root=1;        x->c[1]=y;        y->is_root=0;        if (x->fa!=null){            x->fa->s.erase(x->fa->s.find(x->len1));            if (x->len1==x->fa->mx)                x->fa->mx=(x->fa->s.empty()?-INF:*x->fa->s.rbegin());        }        x->update();    }    return y;}inline Node *mroot(Node *x){    Node *t=access(x);    t->reverse();    return t;}inline void link(Node *u,Node *v){    mroot(u),u->splay();    Node *t=mroot(v);    t->fa=u;    u->s.insert(t->len1);    if (t->len1>u->mx){        u->mx=t->len1;        u->update();    }}Node *find(Node *t,int k){    t->pushdown();    if (k<=t->c[0]->siz)        return find(t->c[0],k);    if (k>t->c[0]->siz+1)        return find(t->c[1],k-t->c[0]->siz-1);    return t;}int main(){    scanf("%d",&n);    *null={null,null,null,0,0,0,-1,-1,-INF};    for (int i=1;i<=n;++i)        d[i]={null,null,null,1,0,1,0,0,-INF};    for (int i=1;i
         
          siz>>1),a->splay(); for (b=a->c[1];b->c[0]!=null;b=b->c[0]) b->pushdown(); b->splay(); b->c[0]=null,b->update(); ans=max(a->len1,b->len2); printf("%d\n",ans); b->c[0]=a,b->update(); } return 0;}
         
        
       
      
     
    

---

总结

如果要让\(LCT\)支持换根操作，并且维护的不满足交换律的东西的时候，要维护它的反向信息。