比赛 20160420s 评测结果 AAAAAATTTA
题目名称 树上的游戏 最终得分 70
用户昵称 asddddd 运行时间 7.422 s
代码语言 C++ 内存使用 6.72 MiB
提交时间 2016-04-20 13:48:41
显示代码纯文本
//
//  main.cpp
//  asd
//
//  Created by Qing Liu on 16/4/20.
//  Copyright 漏 2016骞 Qing Liu. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#define maxn 210000
using namespace std;
vector<int>G[maxn];
void addedge(int from,int to){
    G[from].push_back(to);
    G[to].push_back(from);
}
int L[maxn],R[maxn],cnt,depth[maxn];
pair<int, int> asd[maxn];
void DFS(int o,int pa,int dep){
    L[o]=cnt++;
    depth[o]=dep;
    for (int i=0; i<G[o].size(); i++) {
        int v=G[o][i];
        if(v!=pa)
        DFS(v, o,dep+1);
    }
    R[o]=cnt++;
}
bool in(int a,int b){
    if (L[b]>=L[a]&&R[b]<=R[a]) {
        return true;
    }
    return false;
}
void init(){
    int n;
    cin>>n;
    for (int i=1; i<=n-1; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        addedge(a, b);
        pair<int,int>assd(a,b);
        asd[i]=assd;
    }
    DFS(1, -1, 0);
    int m;
    scanf("%d",&m);
    for (int i=0;i<m; i++) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int l=asd[c].first,r=asd[c].second;
        if (depth[r]>depth[l]) {
            swap(l, r);
        }
        if (in(l, a)^in(l, b)) {
            printf("NO");
        }
        else{
            printf("YES");
        }
    }
}
int main(int argc, const char * argv[]) {
		freopen("treegame.in","r",stdin);
	freopen("treegame.out","w",stdout);
    init();
    return 0;
}