比赛 |
20160420s |
评测结果 |
AAAAAAAAAA |
题目名称 |
树上的游戏 |
最终得分 |
100 |
用户昵称 |
Satoshi |
运行时间 |
3.050 s |
代码语言 |
C++ |
内存使用 |
5.95 MiB |
提交时间 |
2016-04-20 08:26:41 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 200010
using namespace std;
int n,q,L[N],R[N],na[N];
vector<int> G[N];bool vis[N]={0};
class edge
{
public:
int u,v;
void make(int a,int b)
{u=a;v=b;}
void print(){cout<<u<<' '<<v<<' '<<endl;}
}E[N];
int cnt=0;
void haha(int u){L[u]=++cnt;vis[u]=1;for(int i=0;i<G[u].size();i++){int v=G[u][i];if(!vis[v]){na[v]=na[u]+1;haha(v);}}R[u]=cnt;}
void read(){int i,u,v;cin>>n;for(i=1;i<n;i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);E[i].make(u,v);}haha(1);for(i=1;i<n;i++)if(na[E[i].u]>na[E[i].v])swap(E[i].u,E[i].v);}
inline bool killklzwii(int u,int v){return L[u]<=L[v]&&L[v]<=R[u];}
void work(){int i,q,u,v,x,fa;cin>>q;for(i=1;i<=q;i++){scanf("%d%d%d",&u,&v,&x);fa=E[x].v;if(killklzwii(fa,u)^killklzwii(fa,v))printf("NO\n");else printf("YES\n");}}
int main()
{
freopen("treegame.in","r",stdin);
freopen("treegame.out","w",stdout);
read();
work();
return 0;
}