比赛 |
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;
}