【题意】

给一个树，初始点权全部为0，要求你支持如下操作

1.把一个点的点权异或上1   2.查询树上点权为0的两点之间距离最大的距离

【分析】

仍然考虑先建立点分树，然后对于每个点记录如下信息，开两个可删除的优先级队列记录子树内对自己的贡献，和子树内对fa的贡献

动态维护这些信息，查询的时候简单讨论一下，构成一个链即可

【代码】

有亿点点卡常，可能是我在初始化的实现方式上的问题，其实可以在建立点分树的时候直接做一遍点分治

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int head[maxn],tot,q,n;
struct edge
{
    int to,nxt;
}e[maxn<<1];
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
void add(int x,int y)
{
    e[++tot].to=y; e[tot].nxt=head[x]; head[x]=tot;
}
//点分树部分开始___________________________________________________________
int vis[maxn],size,gsiz,siz[maxn],root;
int fa[maxn];
void findrt(int u,int fa)
{
    siz[u]=1;
    int maxsiz=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(vis[to] || to==fa) continue;
        findrt(to,u);
        siz[u]+=siz[to];
        maxsiz=max(maxsiz,siz[to]);
    }
    maxsiz=max(maxsiz,size-siz[u]);
    if(maxsiz<gsiz)
    {
        gsiz=maxsiz;
        root=u;
    }
}
void solve(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(vis[to]) continue;
        size=gsiz=siz[to];
        findrt(to,0);
        fa[root]=u;
        solve(root);
    }
}
//点分树部分开始___________________________________________________________

//可删除优先级队列部分开始_________________________________________________
struct PQ
{
    priority_queue <int> p,q;
    int top()
    {
        while(!q.empty() && p.top()==q.top()) p.pop(),q.pop();
        if(p.empty()) return 0;
        return p.top();
    }
    void pop()
    {
        while(!q.empty() && p.top()==q.top()) p.pop(),q.pop();
        if(!p.empty()) p.pop();
    }
    int size()
    {
        return p.size()-q.size();
    }
    int ctop()
    {
        if(size()<2) return 0;
        int t=top(); pop();
        int ans=top();
        p.push(t); return ans;
    }
};
//可删除优先级队列部分结束_________________________________________________

//ST表O(1)求LCA部分开始____________________________________________________
int st[maxn<<1][20],dfn[maxn],cs,dfstime,lg[maxn<<1];
int dep[maxn];
void dfs(int u,int fa)
{
    dfn[u]=++dfstime;
    st[dfn[u]][0]=dep[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(to==fa) continue;
        dep[to]=dep[u]+1;
        dfs(to,u);
        st[++dfstime][0]=dep[u];
    }    
}
void lca_init()
{
    lg[0]=-1;
    for(int i=1;i<=n*2;i++) lg[i]=lg[i>>1]+1;
    while((1<<(cs+1))<=n*2) cs++;
    for(int j=1;j<=cs;++j)
        for(int i=1;i+(1<<j)-1<=(n<<1);++i)
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int lcadis(int x,int y)
{
    if(dfn[x]>dfn[y]) swap(x,y);
    int i=lg[dfn[y]-dfn[x]+1];
    return min(st[dfn[x]][i],st[dfn[y]-(1<<i)+1][i]);
}
int calcdis(int x,int y)
{
    return dep[x]+dep[y]-2*lcadis(x,y);
}
//ST表O(1)求LCA部分结束____________________________________________________ 

//修改查询部分开始_________________________________________________________ 
PQ A,B[maxn],C[maxn];
//A表示答案，就是拼成的一条链
//B表示所有子节点到自己距离
//C表示所有子节点 
int light[maxn],cntoff;
void turnoff(int u,int v)
{
    if(u==v)
    {
        B[u].p.push(0);
        if(B[u].size()==2) A.p.push(B[u].top());
    }
    if(!fa[u]) return;
    int ff=fa[u],d=calcdis(ff,v),tp=C[u].top();
    C[u].p.push(d);
    if(tp<d)
    {
        int mx=B[ff].top()+B[ff].ctop(),sz=B[ff].size();
        if(tp) B[ff].q.push(tp);
        B[ff].p.push(d);
        int now=B[ff].top()+B[ff].ctop();
        if(now>mx)
        {
            if(sz>=2) A.q.push(mx);
            if(B[ff].size()>=2) A.p.push(now);
        }
    }    
    turnoff(ff,v);
}
void turnon(int u,int v)
{
    if(u==v)
    {
        if(B[u].size()==2) A.q.push(B[u].top()); 
        B[u].q.push(0);
    }
    if(!fa[u]) return;
    int ff=fa[u],d=calcdis(ff,v),tp=C[u].top();
    C[u].q.push(d);
    if(d==tp)
    {
        int mx=B[ff].top()+B[ff].ctop(),sz=B[ff].size();
        B[ff].q.push(d);
        if(C[u].top()) B[ff].p.push(C[u].top());
        int now=B[ff].top()+B[ff].ctop();
        if(now<mx)
        {
            if(sz>=2) A.q.push(mx);
            if(B[ff].size()>=2) A.p.push(now);
        }
    }
    turnon(ff,v);
}
//修改查询部分开始_________________________________________________________
int main()
{

    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    dfs(1,0); lca_init();
    size=gsiz=n; findrt(1,0);
    solve(root);
    for(int i=1;i<=n;i++) C[i].p.push(0);
    for(int i=1;i<=n;i++) light[i]=1;
    for(int i=1;i<=n;i++) turnoff(i,i);
    cntoff=n;
    char op[3];
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%s",op);
        if(op[0]=='G')
        {
            if(cntoff<=1) printf("%d\n",cntoff-1);
            else printf("%d\n",A.top()); 
        }
        else
        {
            x=read();
            if(!light[x]) turnoff(x,x),cntoff++;
            else turnon(x,x),cntoff--;
            light[x]^=1;
        }
    }
    return 0;
}