Submission #4641578

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 100010;
const int MAX_DEPTH = 21;
vector<int> g[MAXV];

int parent[MAXV][MAX_DEPTH];
int depth[MAXV];

void dfs(int v, int p, int d){
    parent[v][0] = 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 s, int n){
    memset(parent, -1, sizeof(parent));
    dfs(s, -1, 0);
    for(int i = 0; i + 1 < MAX_DEPTH; i++){
        for(int v = 0; v < n; v++){
            // 2^k個次に要素がないとき
            if(parent[v][i] < 0) parent[v][i+1] = -1;
            // 2^k個次に要素の2^k個次の要素は2^(k+1)個次の要素
            else parent[v][i+1] = parent[parent[v][i]][i];
        }
    }
}

int lca(int u, int v){
    if(depth[u] > depth[v]) swap(u, v);
    for(int i = 0; i < MAX_DEPTH; i++){
        if(((depth[v] - depth[u]) >> i) & 1){
            v = parent[v][i];
        }
    }
    if(u == v) return u;
    for(int i = MAX_DEPTH - 1; i >= 0; i--){
        if(parent[u][i] != parent[v][i]){
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];
}


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

Submission Info

Judge Result