lca

作者： 作者的头像   多米尼克領主的致意 ,  2024-06-01 07:09:58 ,  所有人可见 ,  阅读 6

0 


#include<iostream>
#include<cstdio>
using namespace std;
const int N=5e5+100,LG=30;
int n,m,t[N],k,deep[N],st[N][LG],x,y,lg[N],s; 
struct node
{
    int id,last;
}a[N*2];
void add(int a1,int a2)//建边
{
    a[++k].id=a2;
    a[k].last=t[a1];
    t[a1]=k;
}
void dfs(int dx,int fa)//预处理出每个结点的深度
{
    deep[dx]=deep[fa]+1;//当前结点深度为父亲结点深度+1
    st[dx][0]=fa;//st表初始值
    for(int i=t[dx];i;i=a[i].last)//递归子结点
    {
        if(a[i].id!=fa) dfs(a[i].id,dx);
    }
}
int lca(int dx,int dy)//求x和y的LCA
{
    if(deep[dx]<deep[dy]) swap(dx,dy);//使得x的深度更深
    for(int i=lg[n];i>=0;i--)//让x跳得跟y一样高
    {
        if(deep[st[dx][i]]>=deep[dy]) dx=st[dx][i]; 
        if(dx==dy) return dx;//x和y重合，LCA为x
    }
    for(int i=lg[n];i>=0;i--)//x和y倍增往上跳，跳到LCA的两个子结点
    {
        if(st[dx][i]!=st[dy][i]) dx=st[dx][i],dy=st[dy][i];
    } 
    return st[dx][0];//再跳一步得到LCA
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        //双向建边，因为不知道父子关系
        add(x,y);
        add(y,x);
    } 
    dfs(s,0);
    for(int i=1;i<=lg[n];i++)//求st表
    {
        for(int j=1;j<=n;j++) st[j][i]=st[st[j][i-1]][i-1];
    }
    while(m--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}

1 评论

用户头像
残阳如血   5个月前      1    踩      回复

树剖 lca：

#include <vector>
#include <iostream>
const int N = 5e5 + 10;

int n, m, s, cnt;
std::vector<int> g[N];
int fa[N], size[N], son[N], dep[N], top[N], dfn[N], rnk[N];

void dfs1(int u, int f) {
    size[u] = 1, dep[u] = dep[fa[u] = f] + 1;
    for (auto v : g[u]) {
        if (v == f) continue;
        dfs1(v, u);
        size[u] += size[v];
        if (size[v] > size[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int ftop) {
    top[u] = ftop, rnk[dfn[u] = ++cnt] = u;
    if (!son[u]) return ;
    dfs2(son[u], ftop);
    for (auto v : g[u]) {
        if (v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int query(int x, int y) {
    while (top[x] != top[y]) { // 不在同一条重链上
        if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cin >> n >> m >> s;
    for (int i = 1, x, y; i < n; ++i) {
        std::cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(s, 0);
    dfs2(s, 0);
    for (int i = 0, a, b; i < m; ++i) {
        std::cin >> a >> b;
        std::cout << query(a, b) << '\n';
    }
    std::cout.flush();
    return 0;
}