首页 > 其他分享 >LCA

LCA

时间:2022-10-20 22:15:52浏览次数:43  
标签:const int cin long add LCA define

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define endl "\n"
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
const int base=131;
const int mod=1e9+7;
const int N=1e5+9,M=1e6+9;
struct pp
{
	int x,y;
}p[N<<1];
int h[N<<1],dep[N],f[N][21];
int n,q,k=0;
void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	for(int i=1;i<=20;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for(int i=h[x];~i;i=p[i].x)
	{
		int y=p[i].y;
		if(y==fa)
			continue;
		f[y][0]=x;
		dfs(y,x);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y])
			x=f[x][i];
		if(x==y)
			return x;
	}
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
void add(int x,int y)
{
	p[k].x=h[x];
	p[k].y=y;
	h[x]=k++;
}
void f0(int T)
{
	cin>>n;
	for(int i=1;i<=n;i++)
		h[i]=-1;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		cout<<dep[x]+dep[y]-2*dep[lca(x,y)]<<endl;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
//	cin>>T;
	for(int i=1;i<=T;i++)
		f0(i);
	return 0;
}

 

标签:const,int,cin,long,add,LCA,define
From: https://www.cnblogs.com/2021sgy/p/16811480.html

相关文章

  • 【图论复习】Tarjan 算法(Tarjan LCA 除外)
    好久没写Tarjan,反正也快CSP了,赶紧复习一下。Tarjan就是基于dfs树中的dfs序以及low数组来进行搜索,注意不同的算法low的更新时不一样的,其他的感觉没什么好讲的......
  • Eclipse插件开发XmlCatalog
    介绍扩展点org.eclipse.wst.xml.core.catalogContributions​......
  • 洛谷P4320 道路相遇(LCA+圆方树)
    题目链接:https://www.luogu.com.cn/problem/P4320道路相遇题目描述在H国的小w决定到从城市$u$到城市$v$旅行,但是此时小c由于各种原因不在城市$u$,但是小c决......
  • adg dumplcate数据库搭建--ora-01537
    dumplicate数据库搭建过程中如下报错  通过以下命令查看相关ora报错信息[oracle@oracle11g~]$oerrora153701537,00000,"cannotaddfile'%s'-filealread......
  • 靶场VNH练习(3)TROLLCAVE: 1.2
    靶场名称:TROLLCAVE:1.2难度:简单目标:拿到root账户的flag文件下载链接:https://www.vulnhub.com/entry/trollcave-12,230/环境搭建使用虚拟机打开ova文件这里没有IP,......
  • 【解题报告】[LNOI 2014] LCA/[GXOI/GZOI 2019] 旧词
    【省选系列】[LNOI2014]LCA/[GXOI/GZOI2019]旧词首黑祭,好耶![LNOI2014]LCA首先考虑,每个节点对答案的贡献,我们可以发现LCA一定会在z到根节点的路径上,每个节点每次增......
  • 2022 ICPC网络赛(二) F Infinity Tree(规律 LCA)
    2022ICPC网络赛(二)FInfinityTree题意:​ 现在给出一个树,对于这棵树,一开始有一个根节点1,每秒之后,每个节点会长出k个节点。节点的最大编号为\(1e18\)。现在给出任意两个......
  • G2. Passable Paths (hard version)-LCA
    G2.PassablePaths(hardversion)https://codeforces.ml/contest/1702/problem/G2题意给你一个树q次询问每次询问一个集合,有m个数\(a_1...a_m\)问这些点组成的路......
  • RMQ求LCA
    RMQ求LCA:使用欧拉序点击查看代码#include<stdio.h>#include<string.h>#include<ctype.h>constintIN_SIZE=200005,OUT_SIZE=200005;charinbuf[IN_SIZE+......
  • LCA(最近公共祖先)求解方法
    本文参考https://oi-wiki.org/graph/lca/定义树上u,v两点的LCA(最近公共祖先)是从根节点dfs到上述两节点路径上距离上述两点最近的公共点。LCA有如下性质:1、u是v的祖先,当且......