题目链接:https://codeforces.ml/contest/1304/problem/E
题目大意:给你一棵树。m次询问。每次询问输入x, y, a, b, k,添加一条x-y的边。问a到b的路径有没有经过k条边的。路径可以重复多次经过多条边和多个点。询问独立(加边仅作用于本次询问)。


思路:我们考虑没有加边的时候。如果k>=dis(x, y)并且k%2==dis(x,y)那么就是可行的。当添加了a-b。可能增加了一条简单路径:dis(x, a)+dis(b, y)+1或者dis(x, b)+dis(a, y)+1。我们判断就可以了。用倍增LCA。计算路径长度。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e5+7;

int n, q, f[18][maxn], h[maxn];
vector<pair<int, int> > v[maxn];
void dfs(int x){
    for(int i=0; i<v[x].size(); i++){
        pair<int, int> t=v[x][i];
        if(t.first==f[0][x]) continue;

        f[0][t.first]=x;
        h[t.first]=h[x]+t.second;
        dfs(t.first);
    }
}

int lca(int x, int y){
    if(h[x]<h[y]) swap(x, y);
    for(int i=17; i>=0; i--){
        if((h[x]-h[y])>>i){
            x=f[i][x];
        }
    }
    if(x==y) return x;
    for(int i=17; i>=0; i--){
        if(f[i][x]!=f[i][y]){
            x=f[i][x];
            y=f[i][y];
        }
    }
    return f[0][x];
}

int dis(int x, int y){
    return h[x]+h[y]-h[lca(x, y)]*2;
}

int check(int x, int y){
    if(x<=y&&x%2==y%2){
        return 1;
    }
    return 0;
}

int main()
{
    int n, a, b;scanf("%d", &n);
    for(int i=1; i<n; i++){
        scanf("%d%d", &a, &b);
        v[a].push_back({b, 1});
        v[b].push_back({a, 1});
    }
    dfs(1);
    for(int i=1; i<=17; i++){
        for(int j=1; j<=n; j++){
            f[i][j]=f[i-1][f[i-1][j]];
        }
    }
    int q, x, y, k;scanf("%d", &q);
    while(q--){
        scanf("%d%d%d%d%d", &x, &y, &a, &b, &k);
        if(check(dis(a, b), k)||check(dis(a, x)+dis(b, y)+1, k)||check(dis(a, y)+dis(b, x)+1, k)){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}