思路与算法

用迭代遍历计算深度与父结点，建立2^j祖先表；每次先把较深点提升到同深度，再同步倍增求LCA，输出dep[x]+dep[y]-2dep[lca]。

正确性说明

树上唯一简单路经过最近公共祖先；两段祖先链长度分别为深度差。倍增先消除深度差，再从大步到小步保留不同祖先的位置，最后一层共同父亲即LCA。

复杂度

O(n log n+Q log n)时间、O(n log n)空间，含邻接表、祖先表、深度初始化及Q项流式输出。

易错点

边长都是1而非带权距离版本；询问在边列表之后单独给Q。用迭代遍历承受100000点深链，相同端点距离0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int L = 1;
    while ((1 << L) <= n)
        L++;
    vector<vector<int>> up(L, vector<int>(n + 1));
    vector<int> dep(n + 1), q(1, 1);
    for (int i = 0; i < (int)q.size(); i++) {
        int u = q[i];
        for (int v : g[u])
            if (v != up[0][u]) {
                up[0][v] = u;
                dep[v] = dep[u] + 1;
                q.push_back(v);
            }
    }
    for (int j = 1; j < L; j++)
        for (int i = 1; i <= n; i++)
            up[j][i] = up[j - 1][up[j - 1][i]];
    int Q;
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        int x = a, y = b;
        if (dep[x] < dep[y])
            swap(x, y);
        int delta = dep[x] - dep[y];
        for (int j = 0; j < L; j++)
            if (delta >> j & 1)
                x = up[j][x];
        if (x != y) {
            for (int j = L - 1; j >= 0; j--)
                if (up[j][x] != up[j][y]) {
                    x = up[j][x];
                    y = up[j][y];
                }
            x = up[0][x];
        }
        cout << dep[a] + dep[b] - 2 * dep[x] << "\n";
    }
}