RT，一道经典LCA模版题 我的代码：

#include <bits/stdc++.h>
using namespace std;
const int tM2 = 31;
const int N = 550005;
int m, dep[N], f[N][tM2 + 2], n, fa[N];
long long res;
vector<int> chid[N];
void bfs_init(int root) {
    queue<int> q;
    q.push(root);
    dep[root] = 1;
    while (!q.empty()) {
        int fr = q.front();
        q.pop();
        for (int i = 0; i < chid[fr].size(); i++) {
            int chd = chid[fr][i];
            if (dep[chd])
                continue;
            dep[chd] = dep[fr] + 1;
            f[chd][0] = fr;
            for (int j = 1; j <= tM2; j++) f[chd][j] = f[f[chd][j - 1]][j - 1];
            q.push(chd);
        }
    }
}
long long qpow(long long a, long long b) {
    long long sum = 1;
    while (b) {
        if (b % 2)
            sum *= a;
        a *= a;
        b >>= 1;
    }
    return sum;
}
int dfs_froot(int x) {
    int fi = x;
    while (1) {
        if (fa[fi] == 0) {
            return fi;
        }
        fi = fa[fi];
    }
}
int lca(int x_, int y_) {
    if (dep[x_] > dep[y_])
        swap(x_, y_);
    for (int i = tM2; i >= 0; i--) {
        if (dep[f[y_][i]] >= dep[x_])
            y_ = f[y_][i], res += qpow(2, i);
    }
    if (x_ == y_)
        return x_;
    for (int i = tM2; i >= 0; i--) {
        if (f[x_][i] != f[y_][i])
            x_ = f[x_][i], y_ = f[y_][i], res += qpow(2, i) * 2;
    }
    res += 2;
    return f[x_][0];
}
int a, b, vs[N];
pair<int, int> x[N];
void init(int rt) {
    for (int i = 1; i < n; i++) {
        if (x[i].first == rt && !vs[x[i].second]) {
            vs[x[i].second] = 1;
            chid[rt].push_back(x[i].second);
            init(x[i].second);
        }
        if (x[i].second == rt && !vs[x[i].first]) {
            vs[x[i].first] = 1;
            chid[rt].push_back(x[i].first);
            init(x[i].first);
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x[i].first, &x[i].second);
    }
    vs[1] = 1;
    init(1);
    bfs_init(1);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &a, &b);
        res = 0;
        int lc = lca(a, b);
        printf("%d\n", lc);
    }
    return 0;
}

交上去TLE了，数据范围1~500w