RMQ求解LCA

loc[i]: 表示 $i$ 在 $dfs$ 序列的下标
dfsx[i], cnt: $0 \sim cnt - 1$ 中记录 $dfs$ 序列

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int N = 2e4 + 6, M = 18;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int f[N][M];
int dfsx[N], cnt;
int loc[N];
int depth[N];

int min(int x, int y) {
    return depth[x] < depth[y] ? x : y;
}

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa) {
    loc[u] = cnt, dfsx[cnt++] = u;
    for(int i = h[u];~i;i = ne[i]) {
        int y = e[i];
        if(y == fa) continue;
        depth[y] = depth[u] + w[i];
        dfs(y, u);
        dfsx[cnt++] = u;
    }
}

int query(int l, int r) {
    if(r < l) swap(l, r);
    int len = r - l + 1;
    int k = log(len) / log(2);
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

void init() {
    memset(f, 0x3f, sizeof f);
    for(int j = 0;j < 17;++j) {
        for(int i = 0;i + (1 << j) - 1 < cnt;++i) {
            if(!j) f[i][j] = dfsx[i];
            else f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    sd(n), sd(m);
    for(int i = 0;i < n - 1;++i) {
        int a, b, c; sd(a), sd(b), sd(c);
        add(a, b, c), add(b, a, c);
    }
    dfs(1, -1);
    init();
    while(--m >= 0) {
        int a, b; sd(a), sd(b);
        int lca = query(loc[a], loc[b]);
        printf("%d\n", depth[a] + depth[b] - 2 * depth[lca]);
    }

    return 0;
}