首页 > 其他分享 >luoguP3379 【模板】最近公共祖先(LCA)

luoguP3379 【模板】最近公共祖先(LCA)

时间:2024-07-22 16:40:03浏览次数:10  
标签:head ch parent int cnt edge luoguP3379 LCA 模板

思路

可以用倍增法去解决问题

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, root, parent[30][600005], dep[600005], head[1000005];
int log_v;
int cnt = 0;
struct e {
	int to, next;
} edge[1000005];
int getint() {
	char ch = '*';
	while (!isdigit(ch = getchar()));
	int num = ch - '0';
	while (isdigit(ch = getchar()))num = num * 10 + ch - '0';
	return num;
}
void add (int x, int y) {
	cnt++;
	edge[cnt].to = y;
	edge[cnt].next = head[x];
	head[x] = cnt;
}
void dfs(int node, int father, int d) {
	parent[0][node] = father;
	dep[node] = d;
	for (int i = head[node]; i != -1; i = edge[i].next) {
		if (edge[i].to != father) dfs(edge[i].to, node, d + 1);
	}
}
void init() {
	dfs(root, -1, 0);
	for (int k = 0; k < log_v - 1; k++) {
		for (int i = 1; i <= n; i++) {
			if (parent[k][i] < 0) parent[k + 1][i] = -1;
			else parent[k + 1][i] = parent[k][parent[k][i]];
		}
	}
}
int LCA(int x, int y) {
	if (dep[x] > dep[y]) swap(x, y);
	for (int i = 0; i < log_v; i++) {
		if (((dep[y] - dep[x]) >> i) & 1) y = parent[i][y];
	}
	if (x == y) return x;
	for (int i = log_v; i >= 0; i--) {
		if (parent[i][x] != parent[i][y]) {
			x = parent[i][x];
			y = parent[i][y];
		}
	}
	return parent[0][x];
}
int main() {
	memset(head, -1, sizeof(head));
	n = getint();
	m = getint();
	root = getint();
	log_v = int(log10(n) / log10(2)) + 1;
	for (int i = 1; i <= n - 1; i++) {
		int x, y;
		x = getint();
		y = getint();
		add(x, y);
		add(y, x);
	}
	init();
	for (int i = 1; i <= m; i++) {
		int x, y;
		x = getint();
		y = getint();
		printf("%d\n", LCA(x, y));
	}
	return 0;
}

标签:head,ch,parent,int,cnt,edge,luoguP3379,LCA,模板
From: https://www.cnblogs.com/mcr130102/p/18316355

相关文章

  • 手写Kd树(C++模板非递归实现)
    手写Kd树(C++模板非递归实现)1.Kd树1.1Kd树简介1.2Kd树的建立1.3Kd树的查找2.C++完整代码实现3.测试代码3.1代码实现3.2测试结果4.与PCL中的Kd树做对比本文实现的Kd树实现参考了高翔博士的书《自动驾驶与机器人中的slam技术从理论到实践》;高博士原书中是递归......
  • [Vani有约会] 雨天的尾巴 /【模板】线段树合并
    [Vani有约会]雨天的尾巴/【模板】线段树合并题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的粮食被弄得一片狼藉。无......
  • 编辑距离与滚动数组优化 - 二维动态规划模板
    题目:编辑距离。思路显然,定义\(f[i][j]\)表示字符串\(a\)中前\(i\)个字符到字符串\(b\)中前\(j\)个字符的编辑距离。那么对于\(a_i=b_j\)时,我们对当前位无需进行任何编辑操作,则\(f[i][j]=f[i-1][j-1]\)。如果\(a_i\neb_j\),那么我们就要对当前位进行编辑:......
  • 易优CMS模板标签downloadpay下载付费
    [基础用法]标签:downloadpay描述:下载模型实现付费,会员专享,会员付费下载,在使用之前先频道模型->下载模型->编辑->开启下载付费使用方法:付费标签需要加载/template/pc/system/download_pay.htm模板文件下载地址:点击下载,该文件放在pc模板目录......
  • 易优CMS模板标签type指定栏目输出单页模型栏目的详细内容
    [基础用法]标签:type描述:获取指定栏目信息用法:{eyou:typetypeid='栏目ID'empty='暂时没有数据'}<ahref="{$field.typeurl}">{$field.typename}</a>{/eyou:type}属性:typeid=''指定栏目ID,如果没有指定则获取当前列表页的栏目IDtype='self'表示当前栏目ty......
  • 最长不降子序列 n log n 方案输出与 Dilworth 定理 - 动态规划模板
    朴素算法不必多说,\(O(n^2)\)的暴力dp转移。优化算法时间为\(O(n\logn)\),本质是贪心,不是dp。思路是维护一个单调栈(手写版),使这个栈单调不降。当该元素\(\ge\)栈顶元素时,把这个元素压入栈中。否则,在单调栈中找到第一个大于该元素的项,把这一项改为这个元素。(因为要......
  • 【搜索】【模板】 IDDFS
    IDDFS使用场景使用dfs由于状态量太大会TLE,bfs会MLE。答案必须很小,一般在20以内。算法原理设置dfs的搜索深度限制\(dep\),dfs穷举\(dep\)层的答案。若在\(dep\)层找到满足条件的情形,则\(dep\)则为答案,否则\(dep\leftarrowdep+1\),继续搜索。优......
  • 【搜索】【模板】记忆化搜索
    记忆化搜索思想是实现DP的一种手段。优点:不关心递推顺序;对于两维及以上的DP,方便处理初始状态和无效状态。缺点:无法使用滚动数组。注意事项:要什么状态搜什么状态;所有的状态转移都要采取直接搜索的数据很傻。越界的状态不能赋值。实现步骤:先判断是否越界,如果越......
  • 【数学】【模板】扩展欧几里得算法
    扩展欧几里得算法思想首先回忆一下裴蜀定理:对于任意一对不全为\(0\)的整数\(a,b\),存在\(x,y\)使得\(ax+by=\gcd(a,b)\)。扩展欧几里得算法就是求出一组解满足\(ax+by=\gcd(a,b)\),这里用到了欧几里得算法,不会的,可以看看我的博客。我们看看怎么求:当\(b=......
  • 【数学】【模板】欧拉定理
    欧拉定理思想若\(a\)与\(n\)互质,则\(a^{\varphi(n)}\equiv1\pmodn\);容易得出当\(n\)为质数时,\(a^{n-1}\equiv1\pmodn\)。证明假设与\(1\simn\)中与\(n\)互质的数字为\(x_1,x_2,x_3,\cdotsx_{\varphi(n)}\),且两两不同。现将它们全部乘以\(a\)得......