这题做的我真是感动

有线段树和动态树分治的做法（话说第一次看到我还以为是动态树的分治【捂脸*ei】），我在考场上面写的是后者，但是当时打错了一个变量，然后爆零了，改完就A了。但是那个题好像数据比较特殊，所以那题代码蒯过来是wa的。于是这种喜闻乐见的东西我重写了一遍，调了一上午，欲仙欲死。

裸题，首先点分治一下，然后用2n个set保存每个分治的重心和它的儿子们的答案，然后对于每次操作就直接添加删除什么的就好了。

当然用优先队列是要比set快一些的。

代码高能

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
struct Set
 {
    multiset <int> li;
    set <int> :: iterator it;
    inline int Sum()
     {return li.size();}
    inline void Ins(int x)
     {li.insert(-x);}
    inline void Del(int x)
     {it=li.lower_bound(-x);li.erase(it);}
    inline int Top()
     {it=li.begin();return it!=li.end()?-*it:0;}
    inline int Sec()
     {it=li.begin();return Sum()<2?0:Top()-*(++it);}
 } a[N*2];
int h[N][20],s[N],n,m,c[N*2][2],fi[N],tot,la[N];
int ss=1,st=0,li[N],sum[N][2],sub[N][20];
int sg[N],rt[N][20],cnt;bool t[N];char b[20];
inline int Read()
 {
    int x=0;char y;
    do y=getchar(); while (y<'0'||y>'9');
    do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
    return x;
 }
inline void Line(int x,int y)
 {
    c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
    c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
 }
int BFS(int x)
 {
    int le=1,ri=1;
    li[1]=x;sum[x][1]=++tot;sum[x][0]=la[x]=0;
    for (;le<=ri;le++)
     for (int i=fi[li[le]];i;i=c[i][1])
      if (!s[c[i][0]]&&sum[c[i][0]][1]!=tot)
        sum[c[i][0]][1]=tot,sum[c[i][0]][0]=0,
        li[++ri]=c[i][0],la[c[i][0]]=li[le];
    for (--le;le;le--)
      sum[la[li[le]]][0]+=++sum[li[le]][0];
    return ri;
 }
void BSF(int x,int y)
 {
    int le=1,ri=1;
    li[1]=x;sum[x][1]=++tot;h[x][y]=0;
    for (;le<=ri;le++)
     for (int i=fi[li[le]];i;i=c[i][1])
      if (!s[c[i][0]]&&sum[c[i][0]][1]!=tot)
        sum[c[i][0]][1]=tot,h[c[i][0]][y]=h[li[le]][y]+1,
        li[++ri]=c[i][0];
    return;
 }
int Find(int x,int y)
 {
    while (1)
     {
        for (int i=fi[x];i;i=c[i][1])
         if (c[i][0]!=la[x]&&sum[c[i][0]][1]==tot&&
            sum[c[i][0]][0]>y/2)
           {x=-c[i][0];break;}
        if (x>0) return x;else x=-x;
     }
 }
void Set_up(int x,int y)
 {
    int k=BFS(x),root=Find(x,k),le=2;BSF(root,y);
    a[sg[root]=sub[root][s[root]=y]=++st].Ins(0);
    if (k==1) {a[0].Ins(0);return;}
    for (int i=fi[root];i;i=c[i][1])
     if (!s[c[i][0]])
       a[sub[c[i][0]][y]=++st].Ins(1),
        rt[c[i][0]][y]=sg[root];
    for (;le<=k;le++)
     for (int i=fi[li[le]];i;i=c[i][1])
      if (!s[c[i][0]]&&!sub[c[i][0]][y])
        a[sub[c[i][0]][y]=sub[li[le]][y]].
          Ins(h[c[i][0]][y]),rt[c[i][0]][y]=sg[root];
    for (int i=fi[root];i;i=c[i][1])
     if (!s[c[i][0]])
       a[sg[root]].Ins(a[sub[c[i][0]][y]].Top());
    a[0].Ins(a[sg[root]].Sec());
    for (int i=fi[root];i;i=c[i][1])
     if (!s[c[i][0]]) Set_up(c[i][0],y+1);
    return;
 }
void Insert(int x)
 {
    for (int i=1;i<s[x];i++)
     {
        int ans=a[sub[x][i]].Top(),Ans,S;
        a[sub[x][i]].Ins(h[x][i]);
        if (h[x][i]<=ans) continue;
        Ans=a[rt[x][i]].Sec();
        if (a[sub[x][i]].Sum()>1) a[rt[x][i]].Del(ans);
        a[rt[x][i]].Ins(a[sub[x][i]].Top());
        S=a[rt[x][i]].Sec();
        if (S!=Ans)
          a[0].Del(Ans),a[0].Ins(S);
     }
    a[sg[x]].Ins(0);
    if (a[sg[x]].Sum()==2) a[0].Ins(a[sg[x]].Sec());
 }
void Delete(int x)
 {
    for (int i=1;i<s[x];i++)
     {
        int ans=a[sub[x][i]].Top(),Ans,S;
        a[sub[x][i]].Del(h[x][i]);
        if (h[x][i]<ans) continue;
        Ans=a[rt[x][i]].Sec();
        a[rt[x][i]].Del(ans);
        if (a[sub[x][i]].Sum())
          a[rt[x][i]].Ins(a[sub[x][i]].Top());
        S=a[rt[x][i]].Sec();
        if (S!=Ans)
          a[0].Del(Ans),a[0].Ins(S);
     }
    int Ans=a[sg[x]].Sec();
    a[sg[x]].Del(0);
    if (a[sg[x]].Sum()==1) a[0].Del(Ans);
 }
int main()
 {
    n=cnt=Read();
    for (int i=1;i<n;i++) Line(Read(),Read());
    Set_up(1,1);m=Read();
    while (m--)
     {
        scanf("%s",b);
        if (b[0]=='G')
          printf("%d\n",cnt<=1?cnt-1:a[0].Top());else
         {
            int k=Read();
            if (t[k]) cnt++,Insert(k);else
              cnt--,Delete(k);
            t[k]=!t[k];
         }
     }
    return 0;
 }