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