求公共祖先LCA

男娘i 2021-12-14 03:45 158阅读 0赞

树剖：

#include<bits/stdc++.h>
    using namespace std;
    const int N=5e5+10;
    struct edge{int to,nex;}e[N*2];
    int n,m,R,cnt=1,head[N],d[N],fa[N],size[N],son[N],top[N];
    void add(int x,int y){
    	e[cnt].to=y;
    	e[cnt].nex=head[x];
    	head[x]=cnt++;
    }
    void dfs1(int u,int f,int depth){
    	d[u]=depth;
    	fa[u]=f;
    	size[u]=1;
    	for(int x,i=head[u];i;i=e[i].nex){
    		x=e[i].to;
    		if(x!=f){
    			dfs1(x,u,depth+1);
    			size[u]+=size[x];
    			if(size[son[u]]<size[x])son[u]=x;
    		}
    	} 
    }
    void dfs2(int u,int tp){
    	top[u]=tp;
    	if(son[u])dfs2(son[u],tp);
    	for(int x,i=head[u];i;i=e[i].nex){
    		x=e[i].to;
    		if(x!=fa[u]&&x!=son[u])
    			dfs2(x,x);
    	}
    }
    int main(){
    	scanf("%d%d%d",&n,&m,&R);
    	for(int x,y,i=1;i<n;i++){
    		scanf("%d%d",&x,&y);
    		add(x,y);
    		add(y,x); 
    	}
    	cnt=0;
    	dfs1(R,0,1);
    	dfs2(R,R);
    	for(int x,y,i=1;i<=m;i++){
    		scanf("%d%d",&x,&y);
    		while(top[x]!=top[y]){
    			if(d[top[x]]>=d[top[y]])x=fa[top[x]];
    			else y=fa[top[y]];
    		}
    		printf("%d\n",d[x]<d[y]?x:y);
    	}
    	return 0;
    }

int lca(int x,int y){
        for(;top[x]!=top[y];){
            if(deep[top[x]]<deep[top[y]])
                swap(x,y);
            x=dad[top[x]];
        }
        if(deep[x]>deep[y])
            swap(x,y);
        return x;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关求二叉树最近公共祖先LCA的brute-force算法

概念先来一张绝妙的百科配图 ![先来一张绝妙的百科配图][70] 最近公共祖先(Lowest/Least Common Ancestor, LCA) > 在图

亦凉/ 2023年10月17日 23:55/ 0 赞/ 65 阅读

相关 [算法系列之三十一]最近公共祖先（LCA）

【简介】对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，

浅浅的花香味﹌/ 2023年06月24日 12:26/ 0 赞/ 8 阅读

相关最近公共祖先LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。 ![2021042810

蔚落/ 2023年01月17日 08:29/ 0 赞/ 93 阅读

相关最近公共祖先LCA(离线Tarjan+在线倍增+MRQ)

[基础理解][Link 1] [全面][Link 2] [Link 1]: https://blog.csdn.net/my_sunshine26/article/de

约定不等于承诺〃/ 2022年10月11日 12:16/ 0 赞/ 121 阅读

相关 LCA 最近公共祖先

[https://www.cnblogs.com/JVxie/p/4854719.html][https_www.cnblogs.com_JVxie_p_4854719.htm

Myth丶恋晨/ 2022年06月02日 11:37/ 0 赞/ 132 阅读

相关最近公共祖先

对于有根树上的两个节点u, v，最近公共祖先`lca(u, v) = x`，x是u, v的祖先并且深度尽可能大 ![一棵树][1240] 对于这棵树来说`lca(9, 1

喜欢ヅ旅行/ 2022年05月13日 07:56/ 0 赞/ 209 阅读

相关求公共祖先LCA

树剖： include<bits/stdc++.h> using namespace std; const int N=5e5+10; str

男娘i/ 2021年12月14日 03:45/ 0 赞/ 159 阅读

相关 LCA最近公共祖先-- HDU 2586

[题目链接][Link 1] Problem Description There are n houses in the village and some bidir

「爱情、让人受尽委屈。」/ 2021年12月01日 17:34/ 0 赞/ 211 阅读

相关最近公共祖先（lca）与树上叉分

lca的定义不在过多解释，代码如下： inline void bfs() { queue<int>q; deep[s]=1

我不是女神ヾ/ 2021年11月29日 23:58/ 0 赞/ 204 阅读

相关倍增求LCA

1 include<iostream> 2 include<cstdio> 3 include<cstring> 4 include<cs

青旅半醒/ 2021年10月26日 18:31/ 0 赞/ 229 阅读