题目链接
这题原来一直T,题解也大多是点分治括号序列等。
我是用边分治写的。
加上快读和O2,这题就过了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;


char buffer[100001],*S,*T;
inline char Get_Char()
{
    if (S==T)
    {
        T=(S=buffer)+fread(buffer,1,100001,stdin);
        if (S==T) return EOF;
    }
    return *S++;
}
inline int read()
{
    char c;int re=0;
    for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
    while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
    return re;
}

inline char read_charA()
{
    char c;
    for(c=Get_Char();c<'A'||c>'Z';c=Get_Char());
    return c;
}

const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=200100;
int head[maxn],ver[maxn*20],edge[maxn*20],nt[maxn*20];
int Head[maxn],Ver[maxn<<1],Edge[maxn<<1],Nt[maxn<<1],tail[maxn],pre[maxn*20];
int d[maxn];
bool ha[maxn];

int nown,n,tot,TOT,root,midedge,maxx,cnt;

void init(void)
{
    memset(head,0,sizeof(head));
    tot=1;
}

void Init(void)
{
    memset(Head,0,sizeof(Head));
    TOT=1;
}

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

void Add(int x,int y,int z)
{
    Ver[++TOT]=y,Edge[TOT]=z;
    Nt[TOT]=Head[x],Head[x]=TOT;
}

void get_pre(void)
{
    memset(tail,0,sizeof(tail));
    for(int x=1;x<=nown;x++)
    {
        for(int i=Head[x];i;i=Nt[i])
        {
            pre[i]=tail[x];
            tail[x]=i;
        }
    }
}

void del(int x,int i)
{
    if(Head[x]==i) Head[x]=Nt[i];
    else Nt[pre[i]]=Nt[i];

    if(tail[x]==i) tail[x]=pre[i];
    else pre[Nt[i]]=pre[i];
}


void build(int x,int fa)
{
    int now=0;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i],z=edge[i];
        if(y==fa) continue;

        if(!now)
        {
            Add(x,y,z),Add(y,x,z);
            now=x;
        }
        else
        {
            ha[++nown]=false;
            Add(nown,now,0),Add(now,nown,0);
            Add(y,nown,z),Add(nown,y,z);
            now=nown;
        }
        build(y,x);
    }
}


void rebuild(void)
{
    Init();
    nown=n;

    for(int i=1;i<=nown;i++) ha[i]=1;

    build(1,0);
    get_pre();

    init();

}


struct point
{
    int y;
    int dis;
    point(){}
    point(int a,int b)
    {
        y=a,dis=b;
    }
    friend bool operator <(const point &a,const point &b)
    {
        return a.dis<b.dis;
    }
};

struct node
{
    int root,midlen,ans;
    int lson,rson;
    priority_queue<point>q;
}t[maxn<<1];

void _init(void)
{
    for(int i=1;i<maxn<<2;i++)
    {
        while(t[i].q.size())
            t[i].q.pop();
        t[i].lson=t[i].rson=0;
    }
    cnt=1;
}

void dfs_size(int x,int fa,int dis)
{
    add(x,root,dis);
    if(ha[x]) t[root].q.push(point(x,dis));
    d[x]=1;

    for(int i=Head[x];i;i=Nt[i])
    {
        int y=Ver[i],z=Edge[i];
        if(y==fa) continue;

        dfs_size(y,x,dis+z);

        d[x]+=d[y];
    }
}


void dfs_midedge(int x,int nowi)
{
    if(max(d[x],d[t[root].root]-d[x])<maxx)
    {
        maxx=max(d[x],d[t[root].root]-d[x]);
        midedge=nowi;
    }

    for(int i=Head[x];i;i=Nt[i])
    {
        int y=Ver[i];
        if(i!=(nowi^1)) dfs_midedge(y,i);
    }
}

void pushup(int id)
{
    t[id].ans=-1;
    while(t[id].q.size()&&ha[t[id].q.top().y]==0) t[id].q.pop();

    int lson=t[id].lson,rson=t[id].rson;

    if(lson==0&&rson==0)
    {
        if(ha[t[id].root]) t[id].ans=0;
    }
    else
    {
        if(t[lson].ans>t[id].ans) t[id].ans=t[lson].ans;
        if(t[rson].ans>t[id].ans) t[id].ans=t[rson].ans;
        if(t[lson].q.size()&&t[rson].q.size())
            t[id].ans=max(t[id].ans,t[lson].q.top().dis+t[rson].q.top().dis+t[id].midlen);
    }
}

void dfs(int id,int x)
{
    root=id,maxx=nown,midedge=0;
    t[id].root=x;

    dfs_size(x,0,0);
    dfs_midedge(x,0);

    if(midedge)
    {
        int p1=Ver[midedge];
        int p2=Ver[midedge^1];

        t[id].midlen=Edge[midedge];

        t[id].lson=++cnt;
        t[id].rson=++cnt;

        del(p1,midedge^1);
        del(p2,midedge);

        dfs(t[id].lson,p1);
        dfs(t[id].rson,p2);

    }
    pushup(id);
}

void update(int x)
{
    ha[x]^=1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i],z=edge[i];
        if(ha[x]==1) t[y].q.push(point(x,z));
        pushup(y);
    }
}

int main(void)
{
    n=read();
    init();
    cnt=1;
    int x,y;
    for(int i=1;i<n;i++)
    {
        x=read(),y=read();
        add(x,y,1);
        add(y,x,1);
    }

    rebuild();
    dfs(1,1);
    int m,pos;
    char str;
    m=read();
    for(int i=1;i<=m;i++)
    {
        str=read_charA();
        if(str=='G')
        {
            if(t[1].ans==-1) printf("They have disappeared.\n");
            else printf("%d\n",t[1].ans);
        }
        else
        {
            pos=read();
            update(pos);
        }
    }
    return 0;
}