记录编号	522128	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAATAATTAA
题目名称	[洛谷3950]部落冲突	最终得分	97
用户昵称	@@@	是否通过	未通过
代码语言	C++	运行时间	20.315 s
提交时间	2018-11-09 07:53:49	内存使用	21.75 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
struct N
{
	int to,i;
}A,B;
vector<N> question[300002];
vector<int> map[300002];
int father[300001];
int b[300001];
int q1[300001],q2[300001];
int battle[300001][2];
int p[300001],ans[300001];
int book[300001],war;
char c[300001];
int cannot[300001];
void build(int x)
{
	for (int i = 0; i < map[x].size(); ++i)
	{
		int t = map[x][i];
		if (father[x] != t)
		{
			father[t] = x;
			build(t);
			/* code */
		}
	}
}
bool pass(int X)
{
	int z = ans[X];
	int x = q1[X],y = q2[X];
	if(x == y)
	{
		return 1;
	}
	while(x != z)
	{
		if (cannot[x] == 1)
		{
			return 0;
			/* code */
		}
		x = father[x];
	}
	while(y != z)
	{
		if (cannot[y] == 1)
		{
			return 0;
			/* code */
		}
		y = father[y];
	}
	return 1;
}
int find(int x)
{
	if (x == b[x])
	{
		return x;
		/* code */
	}
	return b[x] = find(b[x]);
}
int Union(int x,int y)
{
	b[y] = find(x);
}

void dfs(int x)
{
	for (int i = 0; i < map[x].size(); ++i)
	{
		int t = map[x][i];
		if (father[x] != t)
		{
			dfs(t);
			Union(x,t);
			book[t] = 1;
			/* code */
		}
		for (int i = 0; i < question[x].size(); ++i)
		{
			N t = question[x][i];
			if(book[t.to] == 1)
			{
				ans[t.i] = find(t.to);
			}
			/* code */
		}
		/* code */
	}
}
int main()
{
	int i,j;
	ios::sync_with_stdio(false);
	freopen("lct.in","r",stdin);
	freopen("lct.out","w",stdout);
	ios::sync_with_stdio(false);
	
	cin >> n >> m;
	for (int i = 1; i < n; ++i)
	{
		b[i] = i;
		int t1,t2;
		cin >> t1 >> t2;
		map[t1].push_back(t2);
		map[t2].push_back(t1);
		/* code */
	}
	b[n] = n;
	build(1);
	for (int i = 1; i <= m; ++i)
	{
		
		int t1,t2;
		cin >> c[i];
		switch(c[i])
		{
			case 'Q':
			cin >> q1[i] >> q2[i];
			A.to = q2[i];
			A.i = i;
			B.to = q1[i];
			B.i = i;
			question[q1[i]].push_back(A);
			question[q2[i]].push_back(B);
			break; 

			case 'C':
				war++;
			cin >> q1[i] >> q2[i];
			battle[war][0] = q1[i];
			battle[war][1] = q2[i];
			break;

			case 'U':
			cin >> p[i];
			break;
		}
		/* code */
	}
	dfs(1);
	for (int i = 1; i <= m; ++i)
	{
		switch(c[i])
		{
			case 'Q':
			if (pass(i))
			{
				cout << "Yes" << endl;
				/* code */
			}
			else
			{
				cout<< "No" << endl;
			}
			break; 

			case 'C':
				if(father[q1[i]] == q2[i])
			cannot[q1[i]] = 1;
				else
			cannot[q2[i]] = 1;
			break;

			case 'U':
				if(father[battle[p[i]][0]] == battle[p[i]][1])
			cannot[battle[p[i]][0]] = 0;
				else
			cannot[battle[p[i]][1]] = 0;
			break;
		}
		/* code */
	}

	return 0;
}