题目描述

倍增lca

样例

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 1010;

int son[N][2], dep[N] = {0, 1}, d[N], fa[N][20];
#define ls son[id][0]
#define rs son[id][1]

void dfs(int id) {
    if(ls > 0) {
        dep[ls] = dep[id] + 1;
        d[ls] = d[id] + 1;
        fa[ls][0] = id;  // 初始化 fa[ls][0] 为直接父节点
        dfs(ls);
    }
    if(rs > 0) {
        dep[rs] = dep[id] + 1;
        d[rs] = d[id] + 1;
        fa[rs][0] = id;  // 初始化 fa[rs][0] 为直接父节点
        dfs(rs);
    }
}

int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    // 提升 x 到与 y 相同的深度
    for(int i = 10; i >= 0; i--) {
        if(dep[fa[x][i]]  >= dep[y]) x = fa[x][i];
    }
    // 如果此时 x 已经是 y，直接返回
    if(x == y) return x;

    // 同时提升 x 和 y
    for(int i = 10; i >= 0; i--) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];  // 返回他们的父节点
}

void solve() {
    memset(fa, 0, sizeof fa);

    int n, m; cin >> n >> m;
    for(int id = 1; id <= n; id++) {
        int l, r; cin >> l >> r;
        ls = l, rs = r;
    }
    dfs(1);

    // 预处理 fa 数组，构建二进制提升
    for(int j = 1; j <= 10; j++) {
        for(int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j-1]][j-1];
    }

    while(m--) {
        int x1, x2; cin >> x1 >> x2;
        cout << d[x1] + d[x2] - 2 * d[lca(x1, x2)] << '\n';
    }
}

int main() {
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

```