1 - Trees and Queries

#include <bits/stdc++.h>
using namespace std;
const int nax = 100005;

vector<int> adj[nax];
int logaritm[2 * nax];

vector<pair<int,int>> euler;
vector<int> first(nax);
vector<vector<int>> rmq(nax * 2, vector<int> (20, 0));
vector<int> depth(nax);

void dfs(int node, int prd, int lvl) {
    first[node] = euler.size();
    euler.push_back({node, lvl});
    depth[node] = lvl;
    for(auto it : adj[node]) {
        if(it == prd) {
            continue;
        }
        dfs(it, node, lvl + 1);
        euler.push_back({node, lvl});
    }
}

void computeMins() {
    int n = euler.size();
    for(int i = 0; i < n; ++i) {
        rmq[i][0] = i;
    }
    for(int i = 1; (1 << i) <= n; ++i) {
        for(int j = 0; j + (1 << i) - 1 < n; ++j) {
            int k = rmq[j][i - 1];
            int l = rmq[j + (1 << (i - 1))][i - 1];
            if(euler[k].second < euler[l].second) {
                rmq[j][i] = k;
            } else {
                rmq[j][i] = l;
            }
        }
    }
}
int findLCA(int x, int y) {

    x = first[x];
    y = first[y];

    if(x > y) {
        swap(x, y);
    }
    int len = logaritm[y - x + 1];
    int k = rmq[x][len];
    int l = rmq[y - (1 << len) + 1][len];
    if(euler[k].second < euler[l].second) {
        return euler[k].first;
    }
    return euler[l].first;
}

int dist(int x, int y) {
    int lca = findLCA(x, y);
    return depth[x] + depth[y] - 2 * depth[lca];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    logaritm[1] = 0;
    for(int i = 2; i < 2 * nax; i++) {
        logaritm[i] = logaritm[i / 2] + 1;
    }

    int n;
    cin >> n;

    for(int i = 2; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs(1, 0, 0);
    computeMins();

    int m;
    cin >> m;
    for(int i = 1; i <= m; ++i) {

        int x, y, a, b, k, lca;
        cin >> x >> y >> a >> b >> k;
        int dist1 = dist(a, b);
        int dist2 = dist(a, x) + 1 + dist(y, b);
        dist2 = min(dist2, dist(a, y) + 1 + dist(x, b));
        if(dist1 <= k && dist1 % 2 == k % 2) {
            cout << "YES\n";
            continue;
        }
        if(dist2 <= k && dist2 % 2 == k % 2) {
            cout << "YES\n";
            continue;
        }
        cout << "NO\n";
    }

    return 0;
}