比赛 |
20160420s |
评测结果 |
C |
题目名称 |
树上的游戏 |
最终得分 |
0 |
用户昵称 |
debug |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2016-04-20 11:52:26 |
显示代码纯文本
#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");}
}