Poj1330Nearest Common Ancestors LCA

题意给一颗树，再给一个查询两点之间的最近公共祖先。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
const int maxn = 111111;

struct edge
{
    int to; int next;
}e[maxn * 10];
int len;
int head[maxn];
struct Node
{
    int val; int id;
}vis[maxn], dp[maxn][20];
int pos[maxn];
int cnt;
void add(int from, int to)
{
    e[len].to = to;
    e[len].next = head[from];
    head[from] = len++;
}

void dfs(int x, int val)
{
    vis[cnt].val = val; vis[cnt].id = x; pos[x] = cnt++;
    for (int i = head[x]; i != -1; i = e[i].next){
        int cc = e[i].to;
        dfs(cc, val + 1);
        vis[cnt].val = val; vis[cnt].id = x; pos[x] = cnt++;
    }
}

void init(int k)
{
    for (int i = 0; i < k; i++)
        dp[i][0] = vis[i];
    for (int j = 1; (1 << j) <= k; j++){
        for (int i = 0; i + (1 << j) - 1 < k; i++){
            if (dp[i][j - 1].val < dp[i + (1 << (j - 1))][j - 1].val)
                dp[i][j] = dp[i][j - 1];
            else dp[i][j] = dp[i + (1 << (j - 1))][j - 1];
        }
    }
}

int ask(int l, int r)
{
    int k = 0;
    while ((1 << (k + 1)) < r - l + 1) k++;
    if (dp[l][k].val < dp[r - (1 << k) + 1][k].val) return dp[l][k].id;
    else return dp[r - (1 << k) + 1][k].id;
}
int main()
{

    int T; int n;
    cin >> T;
    int root;
    int gg[maxn];
    int a, b;
    while (T--){
        cin >> n;
        len = 0;
        memset(head, -1, sizeof(head));
        for (int i = 1; i <= n; i++) gg[i] = 0;
        for (int i = 0; i<n - 1; i++){
            scanf("%d%d", &a, &b);
            add(a, b); gg[b] = 1;
        }
        for (int i = 1; i <= n; i++) if (!gg[i]) {
            root = i; break;
        }
        cnt = 0;
        dfs(root, 1);
        init(cnt);
        cin >> a >> b;
        int l = pos[a]; int r = pos[b];
        if (l>r) swap(l, r);
        cout << ask(l, r) << endl;
    }
    return 0;
}