比赛 |
20160420s |
评测结果 |
AAAAAAAAAA |
题目名称 |
树上的游戏 |
最终得分 |
100 |
用户昵称 |
KZNS |
运行时间 |
5.279 s |
代码语言 |
C++ |
内存使用 |
36.93 MiB |
提交时间 |
2016-04-20 11:14:30 |
显示代码纯文本
//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