题解 P2056 【[ZJOI2007]捉迷藏 】

· · 题解

LCT也是此题的一种做法。
我们需要的维护的是树上最远关灯点。
LCT是一种链分治，相较于点分治和边分治，链分治不仅需要在变换分治中心的时候维护答案（经过虚边），在一条链中也需要维护答案（经过Splay上的边，也就是实边）。
对于虚边，也就是轻儿子，我们需要求出下面最深的关灯点，更新答案时需要用最深关灯点和另一轻儿子中的最深关灯点来更新，另外还需要考虑当前点是关灯点的情况，和最远点在轻儿子子树中的情况，这些分别用两个堆来分别记录，并在access时维护。
对于Splay上的实边，我们有左儿子和右儿子，左儿子是上半的重链，右儿子是下半重链。那么答案就是左儿子最下点往上的最远距离,和右儿子最上点往下的最远距离，还有当前点的轻儿子最远距离3者的任意一种结合，更新答案。 并继续维护当前链最上点往下，最下点往上的最远距离。
没有link操作的LCT可以只用access+splay完成所有操作，常数并非特别大，甚至可以说十分优秀。
因为需要用堆维护轻儿子的信息，复杂度O(n\log^2 n) 想仔细之后，代码并不难写，只是细节很多。
AC Code:

#include<bits/stdc++.h>
#define maxn 100005
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;

int n;
int info[maxn],Prev[maxn<<1],to[maxn<<1],cst[maxn<<1],cnt_e;
void Node(int u,int v,int c){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v,cst[cnt_e]=c; }
multiset<int>path[maxn],chain[maxn];
int Max(multiset<int>&s){ return s.empty()?-inf:*s.rbegin(); }
int sMax(multiset<int>&s){ return s.size()<=1?-inf:*++s.rbegin(); }

namespace LCT{
    int ch[maxn][2],fa[maxn],val[maxn],lm[maxn],rm[maxn],mx[maxn],w[maxn],sum[maxn];
    #define il inline 
    #define pa fa[x]
    il int inr(int x){ return ch[pa][1]==x; }
    il int isr(int x){ return ch[pa][0]!=x && ch[pa][1]!=x; }
    il void upd(int x){
        int im = max(w[x],Max(chain[x]));
        int Um = max(im,rm[ch[x][0]]+val[x]) , Dm = max(im,lm[ch[x][1]])+val[x];
        lm[x] = max(lm[ch[x][0]],Dm+sum[ch[x][0]]);
        rm[x] = max(rm[ch[x][1]],Um+sum[ch[x][1]]);
        mx[x] = max(
            max(rm[ch[x][0]]+Dm,lm[ch[x][1]]+Um),
            max(max(Max(path[x]),Max(chain[x])+sMax(chain[x])),
            max(mx[ch[x][0]],mx[ch[x][1]])));
        if(w[x]==0) 
            mx[x] = max(mx[x] , max(Max(chain[x]),0));
        sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x];
    }
    il void rot(int x){
        int y = fa[x] , z = fa[y] , c = inr(x);
        if(!isr(y)) ch[z][inr(y)] = x;
        (ch[y][c]=ch[x][!c])&&(fa[ch[y][c]]=y);
        fa[fa[ch[x][!c]=y]=x]=z;
        upd(y);
    }
    il void splay(int x){
        for(;!isr(x);rot(x))
            if(!isr(pa)) rot(inr(pa)==inr(x)?pa:x);
        upd(x);
    }
    il int access(int x,int y=0){
        for(;x;x=fa[y=x]){
            splay(x);
            if(ch[x][1]) path[x].insert(mx[ch[x][1]]),chain[x].insert(lm[ch[x][1]]);
            if(y) path[x].erase(path[x].find(mx[y])),chain[x].erase(chain[x].find(lm[y]));
            ch[x][1] = y , upd(x);
        }
        return y;
    }
}
using namespace LCT;
void dfs(int now,int ff){
    fa[now] = ff; 
    for(int i=info[now];i;i=Prev[i])
        if(to[i]!=ff){
            val[to[i]] = sum[to[i]] = cst[i];
            dfs(to[i],now);
            path[now].insert(mx[to[i]]),
            chain[now].insert(lm[to[i]]);
        }
    upd(now);
}

char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
void read(int &res){
    char ch;bool f = 0;
    for(;!isdigit(ch=getc());) if(ch=='-') f=1;
    for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
    (f) && (res = -res);
}

int main(){
    read(n);
    for(int i=0;i<=n;i++) lm[i]=rm[i]=mx[i]=-inf;
    for(int i=1,u,v;i<n;i++){
        read(u),read(v);
        Node(u,v,1),Node(v,u,1);
    }
    dfs(1,0);
    int ans = mx[1];
    int Q;read(Q);
    for(char s[2];Q--;){
        for(;!isalpha(s[0]=getc()););
        if(s[0]=='C'){
            int x;read(x);
            access(x),splay(x);
            w[x]=(w[x]?0:-inf);
            upd(x),ans=mx[x];
        }
        else ans>=0?printf("%d\n",ans):puts("They have disappeared.");
    }
}