记录编号	252552	评测结果	AAAAAAAAAA
题目名称	树上的游戏	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	5.261 s
提交时间	2016-04-20 16:43:27	内存使用	36.93 MiB

//KZNS
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
//
const int Nmax = 200003;
class poi {
public:
	int x, i, tp;
	poi(){}
	poi(int x, int i, int tp) :
	x(x), i(i), tp(tp) {}
};
//
int N;
vector<int> gp[Nmax];
int rls[Nmax][2] = {0};
stack<poi> stk;
int fa[Nmax] = {0};
int ddp[Nmax] = {0};
int dtm[Nmax] = {0};
int ttmm = 1;
int ST[Nmax*2][20] = {0};
//
inline void fir() {
	scanf("%d", &N);
	for (int i = 1; i < N; i++) {
		scanf("%d%d", &rls[i][0], &rls[i][1]);
		gp[rls[i][0]].push_back(rls[i][1]);
		gp[rls[i][1]].push_back(rls[i][0]);
	}
}
inline void DFS_(int X) {
	stk.push(poi(X, 0, 0));
	int x, i, tp;
	while (!stk.empty()) {
		Wbegin:
		x = stk.top().x;
		i = stk.top().i;
		tp = stk.top().tp;
		stk.pop();
		switch (tp) {
		case 0:
			ddp[x] = ddp[fa[x]] + 1;
			dtm[x] = ttmm;
		case 1:
			for (; i < gp[x].size(); i++) {
				if (!dtm[gp[x][i]]) {
					ST[ttmm++][0] = x;
					fa[gp[x][i]] = x;
					stk.push(poi(x, i+1, 1));
					stk.push(poi(gp[x][i], 0, 0));
					goto Wbegin;
				}
			}
			ST[ttmm++][0] = x;
		}
	}
}
inline int MN(int a, int b) {
	if (ddp[a] < ddp[b])
		return a;
	else
		return b;
}
inline int MX(int a, int b) {
	if (ddp[a] > ddp[b])
		return a;
	else
		return b;
}
inline int loog(int x) {
	int u = 1;
	for (int i = 0; true; i++)
		if (x < (u<<=1))
			return i;
}
inline void setST() {
	for (int j = 1; j <= loog(ttmm); j++)
		for (int i = 1; i+(1<<j)-1 < ttmm; i++)
			ST[i][j] = MN(ST[i][j-1], ST[i+(1<<j-1)][j-1]);
}
inline int LCA(int a, int b) {
	int u;
	a = dtm[a];
	b = dtm[b];
	if (a > b) {
		u = a;
		a = b;
		b = u;
	}
	u = loog(b-a+1);
	return MN(ST[a][u], ST[b-(1<<u)+1][u]);
}
//
int main() {
	freopen("treegame.in", "r", stdin);
	freopen("treegame.out", "w", stdout);
	fir();
	DFS_(1);
	setST();
	int Q;
	scanf("%d", &Q);
	int x, y, z;
	for (int i = 0; i < Q; i++) {
		scanf("%d%d%d", &x, &y, &z);
		z = MX(rls[z][0], rls[z][1]);
		if ((LCA(x,z)==z)^(LCA(y,z)==z))
			printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}
//UBWH