题意

给出一棵边带权的节点数量为 的树，初始树上所有节点都是白色。有两种操作：

• ：改变节点x的颜色，即白变黑，黑变白。
• ：询问树中最远的两个白色节点的距离，这两个白色节点可以重合 (此时距离为 ) 。

  分析

无脑上点分树，每个节点维护两个堆 维护子树中最大的长度 ， 自己对父亲的贡献的最大长度。那么答案就是某一个节点 的权值，就是最大值加次大值。那么点分树维护一下就好了。轻微卡常。总复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 1e5 + 100,inf = 0x3f3f3f3f;
struct Heap {
    priority_queue<int> s,t;
    void add(int x) {s.push(x);}
    void del(int x) {t.push(x);}
    void pre() {while(t.size() && s.top() == t.top()) s.pop(),t.pop();}
    int size() {return s.size() - t.size();}
    int top() {
        pre();if(s.size()) return s.top();
        else -inf;
    }
    int top2() {
        int x = top();del(x);int y = top();add(x);
        return y;
    }
    int ans() {
        if(size() >= 2) return top() + top2();
        else if(size() == 1) return max(top(),0);
        else return -inf;
    }
}A[N],B[N],Ans;
int n,col[N],cnt,Log[N];
struct Edge {int to,nxt,w;}e[N << 1];
int fa[N][21],dep[N],dis[N],head[N],ecnt; 
void addedge(int x,int y,int w) {e[++ecnt]=(Edge){y,head[x],w};head[x] = ecnt;}
int lca(int x,int y) {
    if(dep[x] < dep[y]) swap(x,y);
    int k = dep[x] - dep[y];for(int i = Log[k];~i;i--) {
        if((k >> i) & 1) x = fa[x][i];
    }if(x == y) return x;
    for(int i = Log[dep[x]];~i;i--) {
        if(fa[x][i] ^ fa[y][i]) x = fa[x][i],y = fa[y][i];
    }return fa[x][0];
}
int dist(int x,int y) {return dis[x] + dis[y] - 2 * dis[lca(x,y)];}
void Init(int x,int Fa,int Dep) {
    fa[x][0] = Fa;dep[x] = Dep;
    for(int i = 1;i <= Log[dep[x]];i++) fa[x][i] = fa[fa[x][i-1]][i-1];
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(y == Fa) continue;
        dis[y] = dis[x] + e[i].w;Init(y,x,Dep+1);
    }
}
int rt,maxs[N],size[N],vis[N],dfa[N];
void getrt(int x,int Fa,int tots) {
    size[x] = 1;maxs[x] = 0;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(vis[y] || y == Fa) continue;
        getrt(y,x,tots);size[x] += size[y];
        maxs[x] = max(maxs[x],size[y]);
    }maxs[x] = max(tots - size[x],maxs[x]);
    if(maxs[rt] > maxs[x]) rt = x;
}
void getdis(int x,int Fa,int Di,int rot) {
    B[rot].add(Di);for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(y == Fa || vis[y]) continue;
        getdis(y,x,Di + e[i].w,rot);
    }
}
void Add(int x) {if(A[x].size() >= 2) Ans.add(A[x].ans());} 
void Del(int x) {if(A[x].size() >= 2) Ans.del(A[x].ans());}
void rebuild(int x,int Fa,int tots) {
    vis[x] = 1;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(vis[y]) continue;
        maxs[rt = 0] = inf;
        int Tot = (size[x] < size[y]) ? tots - size[x] : size[y]; 
        getrt(y,x,Tot);
        getdis(y,x,e[i].w,rt);
        A[x].add(B[rt].top());dfa[rt] = x;
        rebuild(rt,x,Tot);
    }A[x].add(0);Add(x);
}

void update(int x) {
    !col[x] ? --cnt : ++cnt;col[x] = 1 - col[x];
    if(col[x]) {Del(x);A[x].del(0);Add(x);}
    else {Del(x);A[x].add(0);Add(x);}
    for(int now = x;dfa[now];now = dfa[now]) {
        int F = dfa[now],d = dist(x,F);
        if(col[x]) {
            Del(F);
            if(B[now].size()) A[F].del(B[now].top());
            if(B[now].size()) B[now].del(d);
            if(B[now].size()) A[F].add(B[now].top());
            Add(F);
        }
        else {
            Del(F);
            if(B[now].size()) A[F].del(B[now].top());
            B[now].add(d);
            A[F].add(B[now].top());
            Add(F);
        }
    }
}
int query() {
    if(cnt >= 2) return max(Ans.top(),0);
    else if(cnt == 1) return 0;
    else return -inf;
}
int main() {
    n = read();
    for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
    for(int i = 1,u,v,w;i < n;i++) {
        u = read();v = read();w = read();
        addedge(u,v,w);addedge(v,u,w);
    }Init(1,0,1);maxs[rt = 0] = inf;getrt(1,0,n);
    rebuild(rt,0,n);int Q = read();cnt = n;
    while(Q--) {
        char ch[10];scanf("%s",ch + 1);
        if(ch[1] == 'A') {
            int res = query();
            if(res <= -inf) printf("They have disappeared.\n");
            else printf("%d\n",res);
        }
        else {int x = read();update(x);}
    }
    return 0;
}