Submission #7499259

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX_V 100000

vector<int> G[MAX_V];
int V;
int par[20][MAX_V], depth[MAX_V];
// par[k][v] := vの2^k先の祖先(根を超すときは-1)

void dfs(int v, int p, int d) {
    par[0][v] = p;
    depth[v] = d;
    for (int i = 0; i < G[v].size(); i++) {
        if (G[v][i] != p) dfs(G[v][i], v, d + 1);
    }
}

void init(int root = 0) {
    dfs(root, -1, 0);
    for (int k = 0; k <= (int)log2(V); k++) {
        for (int v = 0; v < V; v++) {
            if (par[k][v] < 0)
                par[k + 1][v] = -1;
            else
                par[k + 1][v] = par[k][par[k][v]];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k <= (int)log2(V); k++) {
        if ((depth[v] - depth[u]) >> k & 1) {
            v = par[k][v];
        }
    }
    if (u == v) return u;

    for (int k = (int)log2(V); k >= 0; k--) {
        if (par[k][u] != par[k][v]) {
            u = par[k][u];
            v = par[k][v];
        }
    }
    return par[0][u];
}

int main() {
    cin >> V;
    for (int i = 0; i < V - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    init();
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int a, b, c;
        cin >> a >> b;
        a--, b--;
        c = lca(a, b);
        cout << depth[a] + depth[b] - 2 * depth[c] + 1 << endl;
    }
    return 0;
}

Submission Info

Judge Result