lca + sparse table

#include <bits/stdc++.h>

using namespace std;

#define mx 200005
//#define int long long
#define pii pair <int, int>
#define piii pair <int, pii>
#define fi first
#define se second
#define mod 1000000007
#define inf 1e18+19
#define pb push_back
#define si(x) scanf("%lld", &x)
#define mem(ara, x) memset(ara, x, sizeof ara)
#define read() freopen("in.txt", "r", stdin)
#define write() freopen("out.txt", "w", stdout)
#define fst ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

vector <int> g[mx];
int T[mx], P[mx][22], L[mx];

void dfs(int from,int u,int dep){
    T[u]=from;
    L[u]=dep;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(v==from) continue;
        dfs(u,v,dep+1);
    }
}

int lca_query(int N, int p, int q){
    if (L[p] < L[q]) swap(p, q);
    int log = 1;
    while(1){
        int next=log+1;
        if((1<<next)>L[p])break;
        log++;
    }
    for(int i=log;i>=0;i--){
        if (L[p] - (1 << i) >= L[q]){
            p = P[p][i];
        }
    }

    if (p == q)
        return p;

    for(int i = log; i >= 0; i--){
        if(P[p][i] != -1 && P[p][i] != P[q][i]){
            p = P[p][i], q = P[q][i];
        }
    }
    return T[p];
}


void lca_init(int N){
    memset (P,-1,sizeof(P));
    dfs(-1, 0, 0);
    for(int i = 0; i < N; i++){
        P[i][0] = T[i];
    }
    for(int j=1;1<<j<N;j++){
        for(int i=0;i<N;i++){
            if(P[i][j-1]!=-1){
                P[i][j] = P[P[i][j-1]][j-1];
            }
        }
    }
 }

 int dis(int a, int b, int n){
    int c = lca_query(n, a, b);
    return L[a] + L[b] - 2*L[c];
 }

bool check(int dispath, int k){
    if(dispath <= k && dispath %2 == k%2) return true;
    return false;
 }

int32_t main(){
    //read();
    fst;
    int n, q;
    while(cin >> n){
        for(int i=0;i<n-1;i++){
            int u, v;
            cin >> u >> v;
            u--; v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        lca_init(n);
        cin >> q;
        while(q--){
            int x, y, a, b, k;
            cin >> x >> y >> a >> b >> k;
            x--; y--; a--; b--;
            if(check(dis(a, b, n), k)
               ||check(dis(x, a, n) + dis(y, b, n) + 1, k)
               ||check(dis(x, b, n) + dis(y, a, n) + 1, k))
                cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}