比赛 20160420s 评测结果 AAAAAAAAAA
题目名称 树上的游戏 最终得分 100
用户昵称 铁策 运行时间 2.158 s
代码语言 C++ 内存使用 6.60 MiB
提交时间 2016-04-20 10:19:36
显示代码纯文本
#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;
int readint()
{
	int x = 0, c;
	while (!isdigit(c = getchar()));
	do
		x = x * 10 + c - '0';
	while (isdigit(c = getchar()));
	return x;
}
vector<int> tree[200010];
int u[200010], v[200010];
int order[200010], cnt;
int size[200010], dep[200010];
bool vis[200010];
int n, q;
void dfs(int now)
{
	order[now] = cnt++;
	vis[now] = size[now] = 1;
	for (int i = 0; i < (int)tree[now].size(); i++)
	{
		int v = tree[now][i];
		if (!vis[v])
		{
			dep[v] = dep[now] + 1;
			dfs(v);
			size[now] += size[v];
		}
	}
}
int main()
{
	freopen("treegame.in", "r", stdin);
	freopen("treegame.out", "w", stdout);
	n = readint();
	for (int i = 1; i < n; i++)
	{
		int x = readint(), y = readint();
		u[i] = x, v[i] = y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	dfs(1);
	q = readint();
	for (int i = 0; i < q; i++)
	{
		int x, y, z;
		x = readint();
		y = readint();
		z = readint();
		int t = (dep[u[z]] > dep[v[z]] ? u[z] : v[z]);
		int l = order[t], r = order[t] + size[t];
		if ((l <= order[x] && order[x] < r) ^ (l <= order[y] && order[y] < r))
			puts("NO");
		else
			puts("YES");
	}
	return 0;
}