LCA模板

Poj 1330

具体看这篇博客

dep表示深度，fa[u][i]表示u向上跳2^i个点所到的点，fa[u][v]=fa[fa[u][i-1]][i-1]

具体说说为什么从大到小跳，如果从小到大的话也就是从2的0次方开始，间隔越到后面就会越大，最后可能会出现跳超的情况看一张图就明白了

跳到不相等的地方就更新u，v的值，最后u，v一定是在lca(u,v)下面，所以只要输出u的上一个结点也就是fa[u][0]

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=1e4+1;
int fa[maxn][32];
struct node{
    int u,v,next;
}nodes[maxn<<2];
int cnt=0,head[maxn],indo[maxn],dep[maxn];
int n;
void add_node(int u,int v) {
    nodes[cnt]={u,v,head[u]};
    head[u]=cnt++;
}
void init() {
    cnt=0;
    memset(head,-1,sizeof head);
    memset(indo,0,sizeof indo);
}
void dfs(int u,int father) {
    dep[u]=dep[father]+1; 
    fa[u][0]=father;
    for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];~i;i=nodes[i].next) {
        int v=nodes[i].v;
        if(v==father) continue;
        dfs(v,u);
    }
}
int lca(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    int len=dep[u]-dep[v];
    for(int i=0;(1<<i)<=len;i++) {
        if((1<<i)&len) {
            u=fa[u][i];
        }
    }
    if(u==v) return u;
    for(int i=(int)log2(dep[u]);i>=0;i--) {
        if(fa[u][i]!=fa[v][i]) {
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
int main() {
    int t;
    cin>>t;
    while(t--) {
        init();
        cin>>n;
        for(int i=0;i<n-1;i++) {
            int u,v;
            cin>>u>>v;
            add_node(u,v);
            indo[v]++;
        }
        for(int i=1;i<=n;i++) {
            if(indo[i]==0) {
                dfs(i,0);
                break;
            }
        }
        int u,v;
        cin>>u>>v;
        cout<<lca(u,v)<<endl;
    }
    return 0;
}