思路与算法

树的任意两点之间只有一条简单路径，因此不必为每次询问重新运行最短路算法。

以1为根，迭代遍历求深度depth和根距离dist，并记录父亲。倍增表up[k][v]表示v的第2^k级祖先，依公式up[k][v]=up[k-1][up[k-1][v]]填写。

查询u、v时先把较深的点跳到相同深度；若已相同，这一点就是LCA。否则从大到小同时跳到不同的祖先，最后两点的父亲即LCA。输出dist[u]+dist[v]-2*dist[LCA]。

正确性说明

两条根到端点的路径共有根到最近公共祖先的一段。将两条根距离相加，会把这段公共路径计两次；减去两倍LCA根距离后，剩下恰为u到LCA和LCA到v的两段，其并集就是唯一的u-v路径。

倍增先对齐深度，再只在祖先不同的时候同时上移，始终停留在LCA之下；结束后父亲正是两点最深的公共祖先。因此代入公式得到所求距离。同点时LCA就是该点，结果自然为0。

复杂度

n点、m次询问。邻接表、根距离和深度数组初始化与迭代遍历O(n)，祖先表初始化及递推O(n log(n+1))；每次LCA查询O(log(n+1))。总时间O(n log(n+1)+m log(n+1))，空间O(n log(n+1))。

易错点

输入边是双向的，建图需加入两条邻接边，并在遍历时跳过父边。边数为n-1，m表示询问数。注意读取树边长度k，而不是把每条边当1。根的祖先固定为根，便于处理跳转边界；迭代遍历可避免链形树递归过深。两组公开样例都已纳入评测。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Tree {
    int n, L, timer = 0;
    vector<vector<pair<int, ll>>> g;
    vector<vector<int>> up;
    vector<int> d, tin, rev;
    vector<ll> dist;
    Tree(int n) : n(n), L(1), g(n + 1), d(n + 1), tin(n + 1), rev(n + 1), dist(n + 1) {
        while ((1 << L) <= n)
            ++L;
        up.assign(L, vector<int>(n + 1));
    }
    void add(int u, int v, ll w = 1) {
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    void build() {
        vector<int> st(1, 1);
        up[0][1] = 1;
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            tin[u] = ++timer;
            rev[timer] = u;
            for (auto e : g[u])
                if (e.first != up[0][u]) {
                    int v = e.first;
                    up[0][v] = u;
                    d[v] = d[u] + 1;
                    dist[v] = dist[u] + e.second;
                    st.push_back(v);
                }
        }
        for (int k = 1; k < L; ++k)
            for (int u = 1; u <= n; ++u)
                up[k][u] = up[k - 1][up[k - 1][u]];
    }
    int lca(int u, int v) {
        if (d[u] < d[v])
            swap(u, v);
        int x = d[u] - d[v];
        for (int k = 0; k < L; ++k)
            if (x >> k & 1)
                u = up[k][u];
        if (u == v)
            return u;
        for (int k = L - 1; k >= 0; --k)
            if (up[k][u] != up[k][v])
                u = up[k][u], v = up[k][v];
        return up[0][u];
    }
    ll dis(int u, int v) {
        return dist[u] + dist[v] - 2 * dist[lca(u, v)];
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    Tree t(n);
    for (int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        t.add(u, v, w);
    }
    t.build();
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << t.dis(u, v) << '\n';
    }
}