比赛 |
20160420s |
评测结果 |
AAAAAATTTA |
题目名称 |
树上的游戏 |
最终得分 |
70 |
用户昵称 |
asddddd |
运行时间 |
7.422 s |
代码语言 |
C++ |
内存使用 |
6.72 MiB |
提交时间 |
2016-04-20 13:48:41 |
显示代码纯文本
//
// main.cpp
// asd
//
// Created by Qing Liu on 16/4/20.
// Copyright 漏 2016骞 Qing Liu. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#define maxn 210000
using namespace std;
vector<int>G[maxn];
void addedge(int from,int to){
G[from].push_back(to);
G[to].push_back(from);
}
int L[maxn],R[maxn],cnt,depth[maxn];
pair<int, int> asd[maxn];
void DFS(int o,int pa,int dep){
L[o]=cnt++;
depth[o]=dep;
for (int i=0; i<G[o].size(); i++) {
int v=G[o][i];
if(v!=pa)
DFS(v, o,dep+1);
}
R[o]=cnt++;
}
bool in(int a,int b){
if (L[b]>=L[a]&&R[b]<=R[a]) {
return true;
}
return false;
}
void init(){
int n;
cin>>n;
for (int i=1; i<=n-1; i++) {
int a,b;
scanf("%d%d",&a,&b);
addedge(a, b);
pair<int,int>assd(a,b);
asd[i]=assd;
}
DFS(1, -1, 0);
int m;
scanf("%d",&m);
for (int i=0;i<m; i++) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int l=asd[c].first,r=asd[c].second;
if (depth[r]>depth[l]) {
swap(l, r);
}
if (in(l, a)^in(l, b)) {
printf("NO");
}
else{
printf("YES");
}
}
}
int main(int argc, const char * argv[]) {
freopen("treegame.in","r",stdin);
freopen("treegame.out","w",stdout);
init();
return 0;
}