题面原文

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 N,M，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1 行每行包含两个正整数 x, y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 M行每行包含两个正整数 a, b表示询问 a 结点和 b 结点的最近公共祖先。

输出格式

输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。

Ac Record

Code

show me the code.

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn=500001;
vector<int> node[maxn];
int dep[maxn];
int f[maxn][22]; //2^20
int lowbit(int x){
    return log2(x&(-x));
}
void dfs(int u,int fa,int d){
    dep[u]=d;
    f[u][0]=fa;
    for(int i=0;i<node[u].size();++i){
        if(node[u][i]==fa) continue;
        dfs(node[u][i],u,d+1);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]){
        x=f[x][lowbit(dep[x]-dep[y])];
    }
    if(x==y) return x;// or return y.
    for(int i=log2(dep[x]);i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
inline int read()
{
    char c=(char)getchar();
    int x=0,fs=1;
    while(!isdigit(c)){if(c=='-')fs=-1;c=(char)getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=(char)getchar(); //NOLINT
    return x*fs;
}

void write(int a)
{
    if(a<0) putchar('-'),a=-a;
    if(a>=10)write(a/10);
    putchar(a%10+48);
}
int main() {
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<n;++i){
        int x,y;
        x=read();
        y=read();
        node[x].push_back(y);
        node[y].push_back(x);
    }
    dfs(s,s,0);
    for(int i=1;i<22;++i){
        for(int u=1;u<=n;u++){
            f[u][i]=f[f[u][i-1]][i-1];
        }
    }
    for(int i=1;i<=m;++i){
        int x,y;
        x=read();
        y=read();
        cout<<lca(x,y)<<endl;
    }
    return 0;
}

思路

这就是一道LCA模板题。

简单地用vector存图。
先用DFS把整个树遍历一遍，标记上每个节点的深度。这个深度的作用会在后面的算法体现到。
f[u][i]=f[f[u][i-1]][i-1];这是倍增的递推式。
- f[u][i]指的是，节点u的前 $2^i$ 个父节点。
- 例如f[u][0]指的是就是节点u的父节点。f[u][1]指的是就是节点u的父节点的父节点。f[u][2]指的是就是节点u的父节点的父节点的父节点的父节点。
- 在这个题目中的节点数最多是500000，所以最坏情况下是 $2^{19}$ ，所以数组开到20就差不多够用了。（为保险可以多开一点）
用LCA函数求解答案。

int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]){
        x=f[x][lowbit(dep[x]-dep[y])];
    }
    if(x==y) return x;// or return y.
    for(int i=log2(dep[x]);i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}