比赛 20160420s 评测结果 AAAAAAAAAA
题目名称 树上的游戏 最终得分 100
用户昵称 农场主 运行时间 4.481 s
代码语言 C++ 内存使用 100.35 MiB
提交时间 2016-04-20 09:50:03
显示代码纯文本
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define maxn 200200
using namespace std;
vector<int> G[maxn];
int deep[maxn]={0},intree[maxn]={0},st[30][maxn*4]={0},tot=0,dfn[maxn*4]={0},n,u[maxn]={0},v[maxn]={0};
void dfs(int x,int Deep){
	deep[x]=Deep;
	dfn[++tot]=x;
	intree[x]=tot;
	for (int i=0;i<G[x].size();i++) if (!intree[G[x][i]]) {
		dfs(G[x][i],Deep+1);
		dfn[++tot]=x;
	}
	return;
}
int min(int l,int r){
	if (deep[l]<deep[r]) return l;
	else return r;
}
void make_st(){
	for (int i=1;i<=tot;i++) st[0][i]=dfn[i];
	for (int i=1;(1<<i)<=tot;i++){
		for (int j=1;j+(1<<i)-1<=tot;j++){
			st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i)-(1<<(i-1))]);
		}
	}
	return;
}
int LCA(int a,int b){
	int L=intree[a],R=intree[b];
	int r=max(L,R),l=L+R-r,t=(int)log2(r-l+1);
	return min(st[t][l],st[t][r-(1<<t)+1]);
}
bool work(int a,int b,int c,int d){
	int t=LCA(a,b);
	if (LCA(a,c)==c&&LCA(a,d)==d&&LCA(t,c)==t&&LCA(t,d)==t) return 1;
	if (LCA(b,c)==c&&LCA(b,d)==d&&LCA(t,c)==t&&LCA(t,d)==t) return 1;
	return 0;
}
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",&u[i],&v[i]);
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
	}
	dfs(1,0);
	make_st();
	int m,x,y,z;
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		if (work(x,y,u[z],v[z])==1) printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}