首页 > 其他分享 >LCA(最近公共祖先)

LCA(最近公共祖先)

时间:2024-08-14 23:27:51浏览次数:12  
标签:dep par val 祖先 LCA long int ans 公共

参考博客:

最近公共祖先
算法详解之最近公共祖先(LCA)
瓶颈生成树

Tarjan算法

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
using i64 = long long;
int n,m,s;
vector<int> g[N];
vector<pair<int,int>> q[N];
bool st[N];
int p[N];
int find(int x)
{
	if(x!=p[x]) p[x]=find(p[x]);
	return p[x];
}
void add(int a,int b)
{
	int aa=find(a);
	int bb=find(b);
	if(aa!=bb)
		p[bb]=a;
	return ;
}
int idx;
int ans[N];
void tarjan(int u,int f)
{
	st[u]=true;
	for(auto v : g[u])
	{
		if(v==f) continue;
		if(!st[v])
		{
			tarjan(v,u);
		    p[v]=u;
		    st[v]=true;
		}
		
	}
	for(auto w : q[u])
	{
		int v=w.first;
		int id=w.second;
		if(st[v])
		{
			ans[id]=find(v);
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		q[a].push_back({b,i});
		q[b].push_back({a,i});
	}
	tarjan(s,0);
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
}

倍增

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

const int LOGN = 31;
const int N=5e5+10;
int n,q,s;

int dep[N],par[N][LOGN+1],val[N][LOGN+1];
vector<pair<int,int> > e[N];
void dfs(int u,int f)
{
	dep[u] = dep[f] + 1;
	for(auto p : e[u])
	{
		int v=p.first;
		if(v==f) continue;
		par[v][0]=u;
		val[v][0]=p.second;
		dfs(v,u);
	}
}
//求两个点之间的距离最小值
int query(int u,int v)
{
	int ans = 1<<30;
	if(dep[u]>dep[v]) swap(u,v);
	int d=dep[v]-dep[u];
	for(int j=LOGN;j>=0;j--)
	{
		if(d&(1<<j))
		{
			ans=min(ans,val[v][j]);
			v=par[v][j];
		}
	}
	if(u==v) return ans;
	for(int j=LOGN;j>=0;j--) if(par[u][j]!=par[v][j]){
		ans=min(ans,min(val[u][j],val[v][j]));
		u=par[u][j];
		v=par[v][j];
	}
	ans=min(ans,min(val[u][0],val[v][0]));
	return ans;
}
int LCA(int u,int v)
{
	if(dep[u]>dep[v]) swap(u,v);
	int d=dep[v]-dep[u];
	for(int j=LOGN;j>=0;j--)
	{
		if(d&(1<<j))
		{
			v=par[v][j];
		}
	}
	if(u==v) return u;
	for(int j=LOGN;j>=0;j--) if(par[u][j]!=par[v][j]){
		u=par[u][j];
		v=par[v][j];
	}
	return par[u][0];
}
int main()
{
	cin>>n>>q>>s;
	for(int i=1;i<n; i++)
	{
		int u,v,w;
		cin>>u>>v;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	dfs(s,0);
	for(int j = 1;j<=LOGN;j++)
	{
		for(int u=1;u<=n;u++)
		{
			par[u][j]=par[par[u][j-1]][j-1];
			//val[u][j]=min(val[u][j-1],val[par[u][j-1]][j-1]);
		}
	}
	for(int i=1;i<=q;i++)
	{
		int u,v;
		cin>>u>>v;
		cout<<LCA(u,v)<<endl;
	}
}

参考题目

P3379 【模板】最近公共祖先(LCA)
P1967 [NOIP2013 提高组] 货车运输

标签:dep,par,val,祖先,LCA,long,int,ans,公共
From: https://www.cnblogs.com/prioritymygirl/p/18359960

相关文章

  • 【二叉树进阶】--- 二叉搜索树转双向链表 && 最近公共祖先
     Welcometo9ilk'sCodeWorld    (๑•́₃•̀๑) 个人主页:     9ilk(๑•́₃•̀๑) 文章专栏:   数据结构本篇博客我们继续了解一些二叉树的进阶算法。......
  • (CF 10D)最长公共上升子序列(LCIS)(要求输出序列) - 题解
    最长公共上升子序列(LCIS)原题链接:CodeForces、洛谷时间限制:C/C++1000MS,其他语言2000MS内存限制:C/C++256MB,其他语言512MB描述给定两个整数序列,写一个程序求它们的最长上升公共子序列。当以下条件满足的时候,我们将长度\(N\)的序列\(S_1,S_2,...,S_N\)称为长度为\(M......
  • 代码随想录训练营day20|235. 二叉搜索树的最近公共祖先,701.二叉搜索树中的插入操作,450
    二叉搜索树的最近公共祖先题目根据二叉搜索树的特性,它的公共祖先肯定是值夹在p和q之间的(满足此条件的第一个点)TreeNode*getroot(TreeNode*root,TreeNode*p,TreeNode*q){ if(rooot==NULL)returnNULL; if(root->val<p->val&&root->val<q->val){ returngetroot(r......
  • 【树上点差分、LCA】Max Flow P
    核心思路[USACO15DEC]MaxFlowP-洛谷sum[u]++,sum[v]++,sum[lca(u,v)]--,sum[fa[lca(u,v)]];本质上就是,对树进行差分自底向上进行统计处理#include<bits/stdc++.h>usingnamespacestd;intn,m;constintN=200000+10;vector<int>G[N];intdep[N],fa[N],hs......
  • leetcode 718. 最长重复子数组,leetcode 1143. 最长公共子序列
    leetcode718和leetcode1143两道十分相似的题,就不放题目了思路实际上区别就在于一个要求连续数组,另一个要求不连续的序列。二者的dp表达式和状态转移其实是不一致的,前者f[i][j]代表nums1以i结尾nums2以j结尾的最长子数组长度,后者代表nums1以i结尾nums2以j结尾的区间内存......
  • JSP公共卫生综合管控平台md94w(程序+源码+数据库+调试部署+开发环境)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表系统功能:用户,服务站,管控申请,管控记录,申请处理开题报告内容一、项目背景与意义在全球化背景下,公共卫生事件频发,对人民群众的生命安全和身体健康构成严重威......
  • Acetylcarnitine 是一种内源性代谢产物 |MedChemExpress (MCE)
    CAS:14992-62-2品牌:MedChemExpress(MCE)存储条件:4°C,protectfromlight,storedundernitrogen*Insolvent:-80°C,6months;-20°C,1month(protectfromlight,storedundernitrogen)生物活性:Acetylcarnitine是一种内源性代谢产物。 参考详情:Acetylcarni......
  • 关于区块链的公共医疗应用开发
    区块链的养老保险平台应用开发任务一:环境准备1.编译区块链网络目录:/root/xuperchain/在区块链网络目录下执行make命令,编译网络,编译成功后输出compiledone!启动区块链网络2.创建钱包账户创建普通钱包账户userTest,命令如下bin/xchain-cliaccountnewkeys--output......
  • 如何优雅的填充公共字段
    如何优雅的填充公共字段在平时的web开发中,最多的就是编写CRUD逻辑,而CRUD中有很多公共字段,比如创建时间、创建人、更新时间、更新人等,这些字段在每次新增和修改的时候都需要手动填充,这样无疑增加了代码量,降低了开发效率,那么有没有一种优雅的方式来实现这些公共字段的填充呢?1.建......
  • 代码随想录day20 || 235 二叉搜索树最近公共祖先,701 二叉搜索树插入,450,二叉搜索树删除
    235二叉搜索树最近公共祖先unclowestCommonAncestor(root,p,q*TreeNode)*TreeNode{ //本题相较于普通二叉树寻找最近公共祖先加了题设条件二叉搜索树,所以使用二叉搜索树特性 //如果root大于两个目标节点,那么目标都在root左子树 //如果root小于两个目标节点,那么目......