卡常求助

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 500000 + 10;
int fa[maxn][25], h[maxn], lg[maxn];
vector <int> G[maxn];

void dfs(int u, int fath)
{
    fa[u][0] = fath;
    if (fath == -1)   h[u] = 1;
    else    h[u] = h[fath] + 1;
    for (int i = 1; (1 << i) <= h[u]; i++)
    {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    int tn = G[u].size();
    for (int i = 0; i < tn; i++)
    {
        int v = G[u][i];
        if (v != fath)
        {
            fa[v][0] = u;
            dfs(v, u);
        }
    }
}

int lca(int a, int b)
{
    if (h[a] < h[b])    swap(a, b);
    while(h[a] > h[b])
    {
        a = fa[a][lg[h[a] - h[b]] - 1];
    }
    if (a == b)
    {
        return a;
    }
    for (int i = lg[h[a] - 1]; i >= 0; i--)
    {
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}

int main()
{

    ios::sync_with_stdio(false); cin.tie(0);
    int n = 0, m = 0, s = 0;    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int a = 0, b = 0;   cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(s, -1);
    /* for (int i = 1; i <= n; i++)
    {
        printf("x = %d, h = %d\n", i, h[i]);
    } */
    for (int i = 1; i <= n; i++)
    {
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    }
    for (int i = 1; i <= m; i++)
    {
        int a = 0, b = 0;   cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    getchar(); getchar();
    return 0;
}