比赛 20160420s 评测结果 WWAWWWTTTW
题目名称 树上的游戏 最终得分 10
用户昵称 咸鱼二号 运行时间 7.594 s
代码语言 C++ 内存使用 15.58 MiB
提交时间 2016-04-20 11:27:59
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<cstdlib>
#include<iomanip>	//cout<<setiosflags(ios::fixed)<<setprecision(2);
#include<ctime> //double a=(double)clock();	cout<<a<<endl;
#include<vector>
#include<queue>
using namespace std;
const int maxn=200010;
const int INF=(1LL<<31)-1;
inline int read(){
	int x=0,ff=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ff=-1; ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
	return ff*x;
}
inline int mymax(int xx,int yy)
{if(xx<yy)return yy;return xx;}
inline void myswap(int &xx,int &yy)
{xx^=yy,yy^=xx,xx^=yy;}
struct Edge{
	int x,y;
}E[maxn];
int N,M,lin[maxn],len=0,t1,t2,t3,temp;
struct edge{
	int y,next,v;
}e[maxn<<1];
inline void insert(int xx,int yy){
	e[++len].next=lin[xx];
	lin[xx]=len;
	e[len].y=yy;
}
int prev[maxn],top[maxn],tid[maxn],rank[maxn],depth[maxn],sum[maxn],son[maxn],tim=0;
void dfs1(int x,int fa){
	depth[x]=depth[fa]+1;
	sum[x]=1;
	prev[x]=fa;
	for(int i=lin[x];i;i=e[i].next)
		if(e[i].y!=fa){
			dfs1(e[i].y,x);
			if((!son[x])||sum[son[x]]<sum[e[i].y])
				son[x]=e[i].y;
			sum[x]+=sum[e[i].y];
		}
}
void dfs2(int x,int tp){
	tid[x]=++tim;
	rank[tid[x]]=x;
	top[x]=tp;
	if(son[x])
		dfs2(son[x],tp);
	for(int i=lin[x];i;i=e[i].next)
		if(e[i].y!=prev[x]&&e[i].y!=son[x])
			dfs2(e[i].y,e[i].y);
}
int T[maxn<<2];
inline void push_up(int root)
{T[root]=mymax(T[root<<1],T[root<<1|1]);}
void build(int L,int R,int root){
	if(L==R){
		T[root]=1;
		return;
	}
	int mid=(L+R)>>1;
	build(L,mid,root<<1);
	build(mid+1,R,root<<1|1);
	push_up(root);
}
void update(int L,int R,int root,int point,int v){
	if(L==R){
		T[root]=v;
		return;
	}
	int mid=(L+R)>>1;
	if(point<=mid)
		update(L,mid,root<<1,point,v);
	else
		update(mid+1,R,root<<1|1,point,v);
	push_up(root);
}
int query(int L,int R,int root,int l,int r){
	if(l<=L&&r>=R)
		return T[root];
	int mid=(L+R)>>1;
	int f1=1,f2=1;
	if(l<=mid)
		f1=query(L,mid,root<<1,l,r);
	if(r>mid)
		f2=query(mid+1,R,root<<1|1,l,r);
	return mymax(f1,f2);
}
int change(int x,int y){
	while(top[x]!=top[y]){
		if(depth[x]<depth[y])
			myswap(x,y);
		if(query(1,N,1,tid[top[x]],tid[x])==INF)
			return INF;
		x=prev[top[x]];
	}
	if(x!=y){
		if(depth[x]>depth[y])
			myswap(x,y);
		if(query(1,N,1,tid[x]+1,tid[y])==INF)
			return INF;
	}
	return 1;
}
int main(){
	freopen("treegame.in","r",stdin);
	freopen("treegame.out","w",stdout);
	N=read();
	for(int i=1;i<N;i++){
		E[i].x=read(),E[i].y=read();
		insert(E[i].x,E[i].y),insert(E[i].y,E[i].x);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,N,1);
	M=read();
	while(M--){
		t1=read(),t2=read(),t3=read();
		if(depth[E[t3].x]<depth[E[t3].y])
			myswap(E[t3].x,E[t3].y);
		update(1,N,1,tid[E[t3].x],INF);
		temp=change(t1,t2);
		if(temp!=INF)
			printf("YES\n");
		else
			printf("NO\n");
		update(1,N,1,tid[E[t3].x],1);
	}
	return 0;
}