点分治

发表于 | 分类于 | 阅读次数:

##介绍

解决树相关问题的算法的时间复杂度经常与树的深度有关，如果能使树的深度变成 $O(log_2n)$ 级别的，那么很多树相关的问题就迎刃而解了，而实现这一目标的一个重要方法就是树分治。

树分治的中心思想就是将一个规模很大的问题分解为几个两个相同形式的子问题，然后进行合并。

我们首先面临的问题就是如何将一颗树最优地划分为两块，而本文所涉及的点分治便是划分方法的其中一种；其思想主要是以一个点为基准，然后处理过此点的链或点对，至于其它的不断分治下去处理。

我们称作为分治基准点的这个点为重心，那么我们肯定希望它的子树大小比较平均，也就是说，我们要找到一个最大子树最小的点作为重心，具体做法很简单，注意考虑在深度优先遍历意义下作为点祖先的那些点组成的子树即可。

具体做法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool vis[MAXN];int rt;
int mxv[MAXN],mnv;

void calSz(int u,int la)
{
	sz[u]=1,mxv[u]=0;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==la||vis[v]) continue;
		calSz(v,u);
		sz[u]+=sz[v];
		umx(mxv[u],sz[v]);
	}
}

void calRt(int u,int la,int r)
{
	umx(mxv[u],sz[r]-sz[u]);
	if(mxv[u]<mnv) mnv=mxv[u],rt=u;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==la||vis[v]) continue;
		calRt(v,u);
	}
}

void treeDC(int u)
{
	mnv=n;calSz(u,0);calRt(u,0,u);
	vis[rt]=true;
	dfs(rt);
	for(i=G[rt];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v]) continue;
		treeDC(v);
	}	
}

不难证明：点分治的时间复杂度为 $O(nlog_2n)$.

统计点对距离

这是点分治的直接应用，对于每个分治重心计算经过这一重心的点对的贡献。但是这样会产生重复（不是最短路径经过重心的情况），故之后还应减去重复计算的贡献。

常见的问题是求距离 $<,\leq,=,\geq,>k$ 的点对个数。

那么对每个重心统计答案的时候当然不能 $O(n^2)$ 暴力统计，我们可以卡两个指针，$O(n)$ 扫一遍即可。

[POJ1741] Tree

给出一颗 $n$ 个点的树，求距离不大于 $k$ 的点对个数

$n\leq10^4$

这是楼天城男人八题之一，很出名的点分治题目。现在看来当然很裸……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
const int MAXN=1e4+5,MAXM=MAXN<<1;

struct E{int next,to,val;}e[MAXM];int G[MAXN],ecnt;
void addEdge(int u,int v,int w){e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;}

int n,k,vis[MAXN],ans,rt,num;

int mx[MAXN],sz[MAXN],min,dis[MAXN];
void calSz(int u,int fa)
{
	sz[u]=1;mx[u]=0;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=fa&&!vis[v])
		{
			calSz(v,u);
			sz[u]+=sz[v];
			mx[u]=std::max(mx[u],sz[v]);
		}
	}
}

void calRt(int r,int u,int fa)
{
	mx[u]=std::max(mx[u],sz[r]-sz[u]);
	if(mx[u]<min) min=mx[u],rt=u;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=fa&&!vis[v])calRt(r,v,u);
	}
}

void calDis(int u,int d,int fa)
{
	dis[++num]=d;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=fa&&!vis[v]) calDis(v,d+e[i].val,u);
	}
}

int calc(int u,int d)
{
	int res=0;num=0;
	calDis(u,d,0);
	std::sort(dis+1,dis+num+1);
	int i=1,j=num;
	while(i<j)
	{
		while(dis[i]+dis[j]>k&&i<j)j--;
		res+=j-i;i++;
	}
	return res;
}

void dc(int u)
{
	min=n;calSz(u,0);calRt(u,u,0);
	ans+=calc(rt,0);vis[rt]=true;
	for(int i=G[rt];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!vis[v])
		{
			ans-=calc(v,e[i].val);
			dc(v);
		}
	}
}

int main()
{
	while(scanf("%d%d",&n,&k)&&n&&k)
	{
		memset(vis,0,sizeof(vis));
		memset(G,0,sizeof(G));
		ecnt=ans=0;
		int u,v,w;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			addEdge(u,v,w);
			addEdge(v,u,w);
		}
		dc(1);
		printf("%d\n",ans);
	}
	return 0;
}

[BZOJ1316] 树上的询问

给定一棵 $n$ 个节点的树，共 $q$ 次询问，每次询问两点对之间是否存在一个长度为 $L_i$ 的路径。

$n\leq10^4,q\leq100$

询问长度距离某值的点对其实就是小于等于的数量减去小于的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstdio>
#include<algorithm>
using std::min;
inline void umn(int &a,int b){a=min(a,b);}
using std::max;
inline void umx(int &a,int b){a=max(a,b);}

const int MAXN=1e4+5,MAXQ=105;

int n,q;
int qry[MAXQ],ans[MAXQ];

struct E{int next,to,val;} e[MAXN<<1];int ecnt,G[MAXN];
void addEdge(int u,int v,int w){e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;}
void addEdge2(int u,int v,int w){addEdge(u,v,w);addEdge(v,u,w);}

bool vis[MAXN];int rt;
int mxv[MAXN],mnv,sz[MAXN];

void calSz(int u,int la)
{
	sz[u]=1,mxv[u]=0;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==la||vis[v]) continue;
		calSz(v,u);
		sz[u]+=sz[v];
		umx(mxv[u],sz[v]);
	}
}

void calRt(int u,int la,int r)
{
	umx(mxv[u],sz[r]-sz[u]);
	if(mxv[u]<mnv) mnv=mxv[u],rt=u;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==la||vis[v]) continue;
		calRt(v,u,r);
	}
}

int dis[MAXN],dcnt;
void calDis(int u,int la,int d)
{
	dis[++dcnt]=d;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==la||vis[v]) continue;
		calDis(v,u,d+e[i].val);
	}
}

void upd(int u,int d,int flg)
{
	dcnt=0;calDis(u,0,d);
	std::sort(dis+1,dis+dcnt+1);
	int i,k;
	for(i=1;i<=q;i++)
	{
		int l,r;k=qry[i];
		int cnt0=0,cnt1=0;
		for(l=1,r=dcnt;l<r;l++)
		{
			while(dis[l]+dis[r]>=k&&l<r) r--;
			cnt0+=r-l;
		}
		for(l=1,r=dcnt;l<r;l++)
		{
			while(dis[l]+dis[r]>k&&l<r) r--;
			cnt1+=r-l;
		}
		ans[i]+=flg*(cnt1-cnt0);
	}
}

void treeDC(int u)
{
	mnv=n;calSz(u,0);calRt(u,0,u);
	upd(rt,0,1);vis[rt]=true;
	for(int i=G[rt];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v]) continue;
		upd(v,e[i].val,-1);
		treeDC(v);
	}
}

int main()
{
	int i;scanf("%d%d",&n,&q);
	for(i=1;i<n;i++)
	{
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		addEdge2(u,v,w);
	}
	for(i=1;i<=q;i++) scanf("%d",qry+i);
	treeDC(1);
	for(i=1;i<=q;i++)
		if(qry[i]) puts(ans[i]?"Yes":"No");
		else puts("Yes");
	return 0;
}

[BZOJ2152]聪聪可可

给出一颗树，用分数表示出树上所有点对的距离和等于是 $3$ 的倍数的概率。

$n\leq2\times10^4$

难点在分数……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#include<algorithm>

const int MAXN=2e4+5,MAXM=MAXN<<1;

struct E{int next,to,val;} e[MAXM];int G[MAXN],ecnt;
void addEdge(int u,int v,int w){e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;}

int n;
int ans,rt,min,num,mx[MAXN],sz[MAXN],vis[MAXN],dis[MAXN];

void calSz(int u,int fa)
{
	sz[u]=1,mx[u]=0;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=fa&&!vis[v])
		{
			calSz(v,u);
			sz[u]+=sz[v];
			mx[u]=std::max(mx[u],sz[v]);
		}
	}
}

void calRt(int r,int u,int fa)
{
	mx[u]=std::max(mx[u],sz[r]-sz[u]);
	if(min>mx[u]) min=mx[u],rt=u;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=fa&&!vis[v]) calRt(r,v,u);
	}
}
void calDis(int u,int d,int fa)
{
	dis[++num]=d;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=fa&&!vis[v]) calDis(v,d+e[i].val,u);
	}
}

int cnt3[3];
int calc(int u,int d)
{
	num=0;
	calDis(u,d,0);
	for(int i=0;i<3;i++) cnt3[i]=0;
	for(int i=1;i<=num;i++) cnt3[dis[i]%3]++;
	return cnt3[0]*cnt3[0]+cnt3[1]*cnt3[2]*2;
}

void dc(int u)
{
	min=n;calSz(u,0);calRt(u,u,0);
	ans+=calc(rt,0);vis[rt]=true;
	for(int i=G[rt];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!vis[v])
		{
			ans-=calc(v,e[i].val);
			dc(v);
		}
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		addEdge(u,v,w);addEdge(v,u,w);
	}
	dc(1);
	int a=ans,b=n*n;
	int tmp=std::__gcd(a,b);
	printf("%d/%d\n",a/tmp,b/tmp);
}

统计路径条数

路径条数统计的时候就比较简单了，因为不存在重复的问题。

[BZOJ3697]采药人的路径

给定一个 $n$ 个节点的树，每条边都有一个阴阳属性，现在需要选择一条路径，使得中间有一个特殊节点 $p$ （非起点终点）满足从起点到 $p$ 的路径上阴阳平衡，且从 $p$ 到终点的路径上也阴阳平衡。

$n\leq10^5$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<cstdio>
#include<algorithm>
using std::min;
inline void umn(int &a,int b){a=min(a,b);}
using std::max;
inline void umx(int &a,int b){a=max(a,b);}
using std::abs;
typedef long long ll;

const int MAXN=1e5+5;

int n;

struct E{int next,to,val;} e[MAXN<<1];int ecnt,G[MAXN];
void addEdge(int u,int v,int w){e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;}
void addEdge2(int u,int v,int w){addEdge(u,v,w);addEdge(v,u,w);}

bool vis[MAXN];int rt;
int sz[MAXN],mxv[MAXN],mnv;

void calSz(int u,int la)
{
	sz[u]=1,mxv[u]=0;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==la||vis[v]) continue;
		calSz(v,u);
		sz[u]+=sz[v];
		umx(mxv[u],sz[v]);
	}
}

void calRt(int u,int la,int r)
{
	umx(mxv[u],sz[r]-sz[u]);
	if(mxv[u]<mnv) mnv=mxv[u],rt=u;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==la||vis[v]) continue;
		calRt(v,u,r);
	}
}

int mxDis;
int tmp[4][MAXN<<1];
int *C[2]={tmp[0]+MAXN,tmp[1]+MAXN},*c[2]={tmp[2]+MAXN,tmp[3]+MAXN};

void dfs(int u,int la,int d)
{
	static int tmp[MAXN<<1];
	static int *cnt=tmp+MAXN;
	umx(mxDis,abs(d));
	++c[bool(cnt[d])][d];
	++cnt[d];
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==la||vis[v]) continue;
		dfs(v,u,d+e[i].val);
	}
	--cnt[d];
}

inline ll calc(int u)
{
	ll res=0;mxDis=0;
	C[0][0]=1;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v]) continue;
		dfs(v,0,e[i].val);
		res+=(ll)c[0][0]*(C[0][0]-1);
		for(int s=-mxDis;s<=mxDis;s++)
			res+=(ll)c[1][s]*C[0][-s],
			res+=(ll)c[0][s]*C[1][-s],
			res+=(ll)c[1][s]*C[1][-s];
		for(int s=-mxDis;s<=mxDis;s++)
		{
			C[0][s]+=c[0][s];
			C[1][s]+=c[1][s];
		}
		for(int s=-mxDis;s<=mxDis;s++)
			c[0][s]=c[1][s]=0;
	}
	for(int s=-mxDis;s<=mxDis;s++)
		C[0][s]=C[1][s]=0;
	return res;
}

ll ans;
void treeDC(int u)
{
	mnv=n;calSz(u,0);calRt(u,0,u);
	vis[rt]=true;ans+=calc(rt);
	for(int i=G[rt];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v]) continue;
		treeDC(v);
	}
}

int main()
{
	int i;scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		if(!w) w=-1;
		addEdge2(u,v,w);
	}
	treeDC(1);
	printf("%lld",ans);
	return 0;
}

动态点分治

###[BZOJ1095][ZJOI2007] Hide 捉迷藏

有一棵树，初始时每个点都染成黑色，有两种操作：

  • 将一个点的颜色取反；
  • 查询距离最远的两个黑点的距离。

点数 $N\leq10^5$ ，操作数 $Q\leq5\times10^5$.

我们发现：这道题如果没有更改操作的话，就是一道裸的点分治题目。有了更改操作以后，显然我们每一次更改之后都跑一次点分治是不现实的，那么为了充分利用信息，我们考虑将点分治过程中的重心建成一棵重心树（可以证明：中心树的节点数等于原树，且深度不大于 $\log_2n$），然后对于每一个重心开两个堆 $B,C$ ,以动态维护信息。

操作一个重心时，我们将子树上每一个点父重心的距离压进这个重心的 $C$ 堆中，然后将这一中心 $C$ 堆堆顶元素压进其的 $B$ 堆中，也就是说：每个重心的 $B$ 堆存的是其以各儿子为根的子树中到此重心距离的大小；那么我们只要在全局开一个 $A$ 堆，将所有重心的 $B$ 堆的堆顶压进去后， $A$ 堆的堆顶就是答案了。这样，我们只要在更改一个点的颜色时对它和它在重心树上的所有祖先进行一次更新即可。

好了，现在只剩下一个问题了：传统的堆是不支持删除操作的，我们需要使用一种可删堆。具体做法是：开两个堆， $extH,delH$ ，分别表示存在的节点和被删除的节点，删除节点就把它压入 $delH$ 中，取堆顶的时候判断一下是否被删除了，再弹出即可。

因为这道题荒废了半天

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
/**************************************************************
    Problem: 1095
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:18448 ms
    Memory:135668 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
 
const int MAXN=1e5+5;
 
int N,Q;
int fa[MAXN];
bool isOff[MAXN];int offNum;
 
struct E{int next,to;} e[MAXN<<1];int ecnt,G[MAXN];
void addEdge(int u,int v){e[++ecnt]=(E){G[u],v};G[u]=ecnt;}
void addEdge2(int u,int v){addEdge(u,v),addEdge(v,u);}
 
class HEAP
{
    private:
        std::priority_queue<int> extH,delH;
        void clean()
        {
            while(!delH.empty()&&extH.top()==delH.top())
            {
                extH.pop();
                delH.pop();
            }
        }
    public:
        void push(int x){extH.push(x);}
        void del(int x){delH.push(x);}
        void pop(){clean();extH.pop();}
        int top(){clean();return extH.top();}
        int scd()
        {
            int t1=top();pop();
            int t2=top();push(t1);
            return t2;
        }
        int size(){return extH.size()-delH.size();}
} A,B[MAXN],C[MAXN];
 
class LCA
{
    int anc[MAXN][20],dpt[MAXN];
    void dfs(int u,int la)
    {
        for(int i=G[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(v==la) continue;
            dpt[v]=dpt[u]+1;
            anc[v][0]=u;
            dfs(v,u);        
        }
    }
    public:
    void init()
    {
        dfs(1,0);
        for(int i=1;(1<<i)<=N;i++)
            for(int j=1;j<=N;j++)
                anc[j][i]=anc[anc[j][i-1]][i-1];
    }
 
    int calLCA(int x, int y)
    {
        int i;
        if(dpt[x]<dpt[y]) std::swap(x,y);
        int maxlogn=std::floor(std::log(N)/std::log(2));
        for(i=maxlogn;i>=0;i--)
            if(dpt[x]-(1<<i)>=dpt[y])
                x=anc[x][i];
        if(x==y) return x;
        for(i=maxlogn;i>=0;i--)
        {
            if(anc[x][i]!=anc[y][i])
            {
                x=anc[x][i];
                y=anc[y][i];
            }
        }
        return anc[x][0];
    }
 
    int calDis(int x,int y)
    {return dpt[x]+dpt[y]-2*dpt[calLCA(x,y)];}
} lca;
 
class PDC
{
    private:
        int vis[MAXN],rt;
        int mx[MAXN],sz[MAXN],min;
        void calSz(int u,int la)
        {
            sz[u]=1;mx[u]=0;
            for(int i=G[u];i;i=e[i].next)
            {
                int v=e[i].to;
                if(v!=la&&!vis[v])
                {
                    calSz(v,u);
                    sz[u]+=sz[v];
                    mx[u]=std::max(mx[u],sz[v]);
                }
            }
        }
        void calRt(int r,int u,int la)
        {
            mx[u]=std::max(mx[u],sz[r]-sz[u]);
            if(mx[u]<min) min=mx[u],rt=u;
            for(int i=G[u];i;i=e[i].next)
            {
                int v=e[i].to;
                if(v!=la&&!vis[v])calRt(r,v,u);
            }
        }
        void addC(int u,int la)
        {
            C[rt].push(lca.calDis(u,fa[rt]));
            for(int i=G[u];i;i=e[i].next)
            {      
                int v=e[i].to;                                            
                if(v!=la&&!vis[v])
                    addC(v,u);
            }
        }
    public:
        void build(int u,int laRt)
        {
            min=N;
            calSz(u,0);
            calRt(u,u,0);
            vis[rt]=true;fa[rt]=laRt;
            if(laRt) addC(rt,0);
            if(C[rt].size()) B[laRt].push(C[rt].top());
            int oRt=rt;
            for(int i=G[rt];i;i=e[i].next)
            {
                int v=e[i].to;
                if(!vis[v]) build(v,oRt); 
            }
        }
} ptDC;
 
void turnOn(int x)
{
    for(int i=x;fa[i];i=fa[i])
    {
        if(B[fa[i]].size()>=2) A.del(B[fa[i]].top()+B[fa[i]].scd());
        if(C[i].size()) B[fa[i]].del(C[i].top());
        C[i].del(lca.calDis(fa[i],x));
        if(C[i].size()) B[fa[i]].push(C[i].top());
        if(B[fa[i]].size()>=2) A.push(B[fa[i]].top()+B[fa[i]].scd());
    }
}
void turnOff(int x)
{
    for(int i=x;fa[i];i=fa[i])
    {
        if(B[fa[i]].size()>=2) A.del(B[fa[i]].top()+B[fa[i]].scd());
        if(C[i].size()) B[fa[i]].del(C[i].top());
        C[i].push(lca.calDis(fa[i],x));
        if(C[i].size()) B[fa[i]].push(C[i].top());
        if(B[fa[i]].size()>=2) A.push(B[fa[i]].top()+B[fa[i]].scd());
    }
}
 
inline int read()
{                                   
    int x=0,flag=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*flag;
}
 
int main()
{
    int i;
    offNum=N=read();
    for(i=1;i<=N;i++) isOff[i]=true;
    for(i=1;i<N;i++)
    {
        int u,v;u=read();v=read();
        addEdge2(u,v);
    }
    lca.init();
    ptDC.build(1,0);
    for(i=1;i<=N;i++)
        if(B[i].size()>=2)
        {
            A.push(B[i].top()+B[i].scd());
        }
    Q=read();
    char opt[10];
    while(Q--)
    {
        scanf("%s",opt);
        if(opt[0]=='G')
        {
            if(offNum==0) printf("-1\n");
            else if(offNum==1) printf("-1\n");
            else printf("%d\n",A.top());
        }
        else
        {
            int x=read();
            if(isOff[x])
            {
                isOff[x]=false;
                offNum--;
                turnOn(x);
            }else
            {
                isOff[x]=true;
                offNum++;
                turnOff(x);
            }
        }
    }
    return 0;
}