记录编号	307269	评测结果	AAAAAATATA
题目名称	树上的游戏	最终得分	80
用户昵称	农场主	是否通过	未通过
代码语言	C++	运行时间	8.544 s
提交时间	2016-09-14 14:57:59	内存使用	36.34 MiB

#include <iostream>
#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;
const int nmax=400086;
const int vmax=20;
int n,q;
int s=0;
int tmpu,tmpv;
int au,av;
int tmpnode;
int predeep;
int smin[nmax][vmax];
int list[nmax];
int pos[nmax],deep[nmax];
bool vis[nmax];
class edge
{
public:
	int u,v;
};
vector<edge> edges;
vector<int > G[nmax];
inline void PreDo()
{
	scanf("%d",&n);
	deep[0]=0;
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&tmpu,&tmpv);
		edges.pb((edge){tmpu,tmpv});
		G[tmpu].pb(edges.size()-1);
		edges.pb((edge){tmpv,tmpu});
		G[tmpv].pb(edges.size()-1);
	}

}
void DFS(int x)
{
	vis[x]=1;
	s++;
	list[s]=x;
	pos[x]=s;
	for(int i=0;i<G[x].size();i++)
	{
		if(vis[edges[G[x][i]].v]==0)
		{
			deep[edges[G[x][i]].v]=deep[edges[G[x][i]].u]+1;
			DFS(edges[G[x][i]].v);
			s++;
			list[s]=x;
		}
	}
}

inline int minx(int a,int b)
{
	if(deep[a]<deep[b])
		return a;
	else
		return b;
}

inline void RMQ()
{
	for(int i=1;i<=s;i++)
		smin[i][0]=list[i];
	for(int j=1;j<vmax;j++)
		for(int i=1;i<=s;i++)
			if(i+(1<<j)-1<=s)
				smin[i][j]=minx(smin[i][j-1],smin[i+(1<<(j-1))][j-1]);
}
inline void exchangea(int &tmpu,int &tmpv)
{
	if(pos[tmpu]>pos[tmpv])
	{
		int tmp;
		tmp=tmpu;
		tmpu=tmpv;
		tmpv=tmp;
	}
}
inline void exchangeu(int &nodeu,int &nodelca)
{
	if(pos[nodeu]>pos[nodelca])
	{
		int tmp;
		tmp=nodeu;
		nodeu=nodelca;
		nodelca=tmp;
	}
}
inline void exchangev(int &nodev,int &nodelca)
{
	if(pos[nodev]>pos[nodelca])
	{
		int tmp;
		tmp=nodev;
		nodev=nodelca;
		nodelca=tmp;
	}
}
inline int log2(int x){
	int t=1;
	int tot=0;
	while (1){
		if (t>x) return tot-1;
		t=t<<1;
		tot++;
	}
}
inline int LCA(int x,int y)//传入的是某编号的节点对应的位置
{
	if(y<x)
	{
		int tmp=y;
		y=x;
		x=tmp;
	}
	int k=log2(y-x+1);
	int lca=minx(smin[x][k],smin[y-(1<<k)+1][k]);
	return lca;
}
inline void exchange()
{
	if(pos[tmpu]>pos[tmpv])
	{
		int tmp=tmpu;
		tmpu=tmpv;
		tmpv=tmp;
	}
}

int main()
{
	//printf("%d",log2(3));
	freopen("treegame.in","r",stdin);
	freopen("treegame.out","w",stdout);
	PreDo();
	DFS(1);
	RMQ();
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&au,&av,&tmpnode);
		int lcanode=LCA(pos[au],pos[av]);
		//printf("%d\n",lcanode);
		int du=edges[tmpnode*2-2].u;
		int dv=edges[tmpnode*2-2].v;
		int predeep;
		if(deep[du]<deep[dv])
			predeep=du;
		else
			predeep=dv;
		int lcalca=LCA(pos[lcanode],pos[predeep]);
		if(lcalca!=lcanode)
		{
			printf("YES\n");
		}
		else
		{
			int lcalu=LCA(pos[au],pos[du]);
			int lcalv=LCA(pos[au],pos[dv]);
			int lcaru=LCA(pos[av],pos[du]);
			int lcarv=LCA(pos[av],pos[dv]);
			if(lcalu==du&&lcalv==dv)
				printf("NO\n");
			else
			{
				if(lcaru==du&&lcarv==dv)
					printf("NO\n");
				else
					printf("YES\n");
			}
		}
	}
	return 0;
}