Description：

一棵树上有黑点和白点，支持反转某个点的颜色和询问最长的两个白点的距离。

$1\le n \le 200000$

Solution：

动态点分治，先把点分树建出来，然后每个节点维护两个堆，第一个堆维护这个点在点分树上的子节点到点分树上的父亲的值，第二个堆维护这个点的子树中的节点到他的值，第一个堆就是儿子节点的第二个堆的堆顶组成的，每次反转某个染色时不断在点分树上跳父亲并修改这两个堆，还要维护一个全局的堆记录最长距离，就是各个点的第二个堆最大和次大之和组成的，查询时直接返回堆顶。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

#define MAXN 100010

int n,m;

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

struct heap

{

	priority_queue<int> add,del;

	void push(int x){add.push(x);}

	void erase(int x){del.push(x);}

	void pop()

	{

		while(!del.empty() && add.top() == del.top())

			add.pop(),del.pop();

		add.pop();

		return;

	}

	int fi()

	{

		while(!del.empty() && add.top() == del.top())

			add.pop(),del.pop();

		if(add.empty())return 0;

		return add.top();

	}

	int siz(){return add.size() - del.size();}

	int se()

	{

		if(siz() < 2)return 0;

		int x = fi();pop();

		int y = fi();push(x);

		return y;

	}

}qa,qb[MAXN],qc[MAXN];

int top[MAXN],dep[MAXN],fu[MAXN],siz[MAXN],son[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fu[k])

		{

			fu[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != son[k] && e[i].to != fu[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fu[top[a]];

	}

	return dep[a] < dep[b] ? a : b;

}

int dis(int x,int y){return dep[x] + dep[y] - 2 * dep[LCA(x,y)];}

int size[MAXN],d[MAXN],s,root;

bool v[MAXN];

void getroot(int k,int fa)

{

	size[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa && !v[e[i].to])

		{

			getroot(e[i].to,k);

			size[k] += size[e[i].to];

			d[k] = max(d[k],size[e[i].to]);

		}

	}

	d[k] = max(d[k],s - size[k]);

	if(d[k] < d[root])root = k;

	return;

}

int fa[MAXN];

void divide(int k,int f)

{

	fa[k] = f;v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			s = size[e[i].to];root = 0;

			getroot(e[i].to,k);

			divide(root,k);

		}

	}

	return;

}

void turn_off(int u,int v)

{

	if(u == v)

	{

		qb[u].push(0);

		if(qb[u].siz() == 2)qa.push(qb[u].fi());

	}

	if(!fa[u])return;

	int f = fa[u],d = dis(f,v),tmp = qc[u].fi();

	qc[u].push(d);

	if(d > tmp)

	{

		int mx = qb[f].fi() + qb[f].se(),size = qb[f].siz();

		if(tmp)qb[f].erase(tmp);

		qb[f].push(d);

		int now = qb[f].fi() + qb[f].se();

		if(now > mx)

		{

			if(size >= 2)qa.erase(mx);

			if(qb[f].siz() >= 2)qa.push(now);

		}

	}

	turn_off(f,v);

	return;

}

void turn_on(int u,int v)

{

	if(u == v)

	{

		if(qb[u].siz() == 2)qa.erase(qb[u].fi());

		qb[u].erase(0);

	}

	if(!fa[u])return;

	int f = fa[u],d = dis(f,v),tmp = qc[u].fi();

	qc[u].erase(d);

	if(d == tmp)

	{

		int mx = qb[f].fi() + qb[f].se(),size = qb[f].siz();

		qb[f].erase(d);

		if(qc[u].fi())qb[f].push(qc[u].fi());

		int now = qb[f].fi() + qb[f].se();

		if(now < mx)

		{

			if(size >= 2)qa.erase(mx);

			if(qb[f].siz() >= 2)qa.push(now);

		}

	}

	turn_on(f,v);

	return;

}

inline char getc()

{

	register char c = getchar();

	while(c != 'G' && c != 'C')c = getchar();

	return c;

}

int state[MAXN];

int main()

{

	scanf("%d",&n);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs1(1,1);dfs2(1,1);

	root = 0;d[0] = INF;s = n;

	getroot(1,0);

	divide(root,0);

	for(int i = 1;i <= n;++i)qc[i].push(0);

	int tot = 0;

	for(int i = 1;i <= n;++i)

	{

		state[i] = 1;

		turn_off(i,i);

		++tot;

	}

	scanf("%d",&m);

	char c;int k;

	for(int i = 1;i <= m;++i)

	{

		c = getc();

		if(c == 'G')

		{

			if(tot <= 1)printf("%d\n",tot - 1);

			else printf("%d\n",qa.fi());

		}

		else

		{

			scanf("%d",&k);

			if(state[k]){turn_on(k,k);--tot;}

			else{turn_off(k,k);++tot;}

			state[k] ^= 1;

			

		}

	}

	return 0;

}