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

#include<cstdio>
using namespace std;
int weizhi[444444]={};int shuliang[444444]={};int num[444444]={};int n,m;int x,y,z;int gug=1;int yyy;struct ff{int x,y;}f[444444]={};int e[444444]={};int maxsize[444444]={};bool flag=0;bool flag2=0;
int num0[444444]={};int idd[444444]={};int tou,wei;int q[444444]={};int top[444444]={};int gen[444444]={},dep[444444]={},son[444444]={},siz[444444]={};bool vis[444444]={};int id[444444]={};int tot=0;int rudu[444444]={};
int max(int a,int b){return a<b?b:a;}
void ggg(){
	tou=0,wei=0;q[0]=1;while(tou<=wei){int te=q[tou];
	for(int i=weizhi[te];i<weizhi[te+1];i++)if(e[i]!=gen[te])gen[e[i]]=te,q[++wei]=e[i],dep[e[i]]=dep[te]+1;tou++;}
	for(int i=1;i<=n;i++)rudu[i]=shuliang[i]-1;tou=0,wei=-1;rudu[1]++;
	for(int i=1;i<=n;i++)if(rudu[i]==0)q[++wei]=i;
	while(tou<=wei){
		int te=q[tou];rudu[gen[te]]--;if(rudu[gen[te]]==0)q[++wei]=gen[te];siz[te]=1;
		for(int i=weizhi[te];i<weizhi[te+1];i++)if(e[i]!=gen[te])siz[te]+=siz[e[i]];tou++;}
	for(int i=1;i<=n;i++){for(int j=weizhi[i];j<weizhi[i+1];j++)
			if(e[j]!=gen[i])if(siz[e[j]]>maxsize[i])maxsize[i]=siz[e[j]],son[i]=e[j];}
	tou=0,wei=0;q[0]=1;tot=0;id[1]=1;
	while(tou<=wei){
		int te=q[tou];for(int i=weizhi[te];i<weizhi[te+1];i++)if(e[i]!=gen[te])q[++wei]=e[i];
		if(!vis[te]){vis[te]=1;tot=id[te];top[te]=te;int tm=te;while(son[te]!=0)te=son[te],id[te]=++tot,vis[te]=1,top[te]=tm;}
		te=q[tou];int tee=id[te]+1+maxsize[te];
		for(int i=weizhi[te];i<weizhi[te+1];i++){if(vis[e[i]]||e[i]==gen[te])continue;id[e[i]]=tee,tee+=siz[e[i]];}tou++;}}
int lca(int a,int b){while(top[a]!=top[b]){if(dep[top[a]]>dep[top[b]])a=top[a],a=gen[a];else b=top[b],b=gen[b];}if(dep[a]>dep[b])return b;else return a;}
void check(int a,int b,int c){c=id[c];while(top[a]>top[b]){if(id[top[a]]<=c&&id[a]>=c){flag=1;return;}a=top[a];a=gen[a];}if(id[b]<=c&&id[a]>=c)flag=1;return;}
void check2(int a,int b,int c){c=id[c];while(top[a]>top[b]){if(id[top[a]]<=c&&id[a]>=c){flag2=1;return;}a=top[a];a=gen[a];}if(id[b]<=c&&id[a]>=c)flag2=1;return;}
inline int read(){int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x;}
int main(){
	freopen("treegame.in","r",stdin);freopen("treegame.out","w",stdout);
	scanf("%d",&n);for(int i=1;i<n;i++)scanf("%d%d",&f[i].x,&f[i].y),shuliang[f[i].x]++,shuliang[f[i].y]++;
	for(int i=1;i<=n+1;i++)weizhi[i]=weizhi[i-1]+shuliang[i-1];
	for(int i=1;i<n;i++)e[weizhi[f[i].x]]=f[i].y,e[weizhi[f[i].y]]=f[i].x,num0[weizhi[f[i].x]]=num0[weizhi[f[i].y]]=i,weizhi[f[i].x]++,weizhi[f[i].y]++;
	for(int i=n+1;i>0;i--)weizhi[i]=weizhi[i-1];
	ggg();while(gug<n)gug<<=1;scanf("%d",&yyy);int x,y,z,temp;
	for(int ii=1;ii<=yyy;ii++){
		x=read(),y=read(),z=read();temp=f[z].x;int zz=lca(x,y);flag=0;flag2=0;
		check(x,zz,temp);if(!flag)check(y,zz,temp);temp=f[z].y;check2(x,zz,temp);if(!flag2)check2(y,zz,temp);
		if(flag&&flag2)printf("NO\n");else printf("YES\n");}
}