题目

https://vjudge.net/problem/POJ-1330

思路

LCA中的倍增解法

① 用二维数组 t r e e [ x ] [ y ] tree[x][y] tree[x][y]存储这棵树,x为父节点,y为子节点,使用vector便于DFS
② 用de数组确定根节点:深度为0
③ 用h数组确定所有结点的深度:子节点=父节点深度+1
④ 倍增

• 先从1,2,4,8…依次跳着找到前面的祖先,保存到 f a [ x ] [ y ] fa[x][y] fa[x][y]中,y表示2的y次方,如 f a [ 3 ] [ 0 ] = 16 , f a [ 3 ] [ 1 ] = 10 , f a [ 3 ] [ 2 ] = 8 , f a [ 3 ] [ 3 ] = 0 fa[3][0]=16,fa[3][1]=10,fa[3][2]=8,fa[3][3]=0 fa[3][0]=16,fa[3][1]=10,fa[3][2]=8,fa[3][3]=0

    fa[ch][0] = rr;
    for (int i = 1; i < 20; ++i)
    {
        fa[ch][i] = fa[fa[ch][i - 1]][i - 1];  //fa[3][2]=fa[10][1]
        //就是3到8的距离是10到8的一半,所以i-1
        //10就是中点那个~
    }

• 再把a上升到与b一个高度:…8,4,2,1(1<<i)的尝试,比如两个数相差的深度为13,可以通过依次跳8→4→1实现(即i依次取3,2,0)
• 最后a,b一起往上跳,也是从…8,4,2,1开始,祖先不相等时(求最近的祖先)一起往上跳,最小不相等的上一个就是公共祖先辽

代码

#include <iostream>
#include <vector>
#include <cstring>

#define MAXX 200005
using namespace std;
vector<int> tree[MAXX];
int h[MAXX];
int de[MAXX];
int fa[MAXX][20];

void DFS(int rr, int ch)
{
    h[ch] = h[rr] + 1;
    fa[ch][0] = rr;
    for (int i = 1; i < 20; ++i)
    {
        fa[ch][i] = fa[fa[ch][i - 1]][i - 1];
    }
    for (int i = 0; i < tree[ch].size(); ++i)
    {
        DFS(ch, tree[ch][i]);
    }
}

int LCA(int a, int b)
{
    if (h[a] < h[b])
        swap(a, b);
    if (a == b)
        return a;
    for (int i = 19; i >= 0; i--)  //同一高度
    {
        if (h[a] - (1 << i) >= h[b])
            a = fa[a][i];
    }
    if (a == b)
        return a;
    for (int i = 19; i >= 0; i--)  //一起跳
    {
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}

int main()
{
    int N, n, r;
    cin >> N;
    while (N--)
    {
        //清零*******
        memset(h, 0, sizeof(h)); //两个数组,虽然都是高度,意义不同
        memset(de,0,sizeof de);
        cin >> n;
        for (int i = 0; i < n - 1; ++i)
        {
            int x, y;
            cin >> x >> y;
            tree[x].push_back(y);
            de[y]++;
        }
        for (int i = 1; i <= n; ++i)  //从1开始
        {
            if (de[i] == 0)
            {
                r = i;
                break;
            }
        }
        DFS(0, r);
        int a, b;
        cin >> a >> b;
        cout << LCA(a, b) << endl;
        for (int i = 1; i <= n; ++i)   //清楚
        {
            tree[i].clear();
        }
    }
    return 0;
}

注意

① MAXX取值小了是RE,大了是MLE…CE是因为用了2e5+5