526互联

二叉树的最近公共祖先

发布时间 2023-11-26 19:02:23作者: 加固文明幻景

二叉树的最近公共祖先

概述

对于两个节点 \(u\)、\(v\)，找到一个深度最大的 \(x\)，\(x\) 是 \(u\) 、\(v\) 的祖先。

则 \(x\) 为这两个节点的最近公共祖先（LCA）。

初始方法

对于 \(u\) 或 \(v\)：

从该结点一直向上找祖先，知道找到整棵树的根节点，在对应数组存下每一个祖先。

那么对于两个数组，从后往前扩增的子序列（倒数第一个都是根节点，肯定相同），最后一个符合条件的即 \(\texttt {LCA}\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 500000 + 10;

struct Node
{
	int l, r, fa;
} a[N];

int n, c[N], d[N];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n ;
	//假设以这种形式读入
	for (int i = 1; i <= n; i++)
	{
		int x, y;
		std::cin >> x >> y;
		if (x)
			a[i].l = x, a[x].fa = i;
		if (y)
			a[i].r = y, a[y].fa = i;
	}
	int u, v;
	std::cin >> u >> v;
	int l1 = 0;
	while (u != 1) //根节点假设是1
	{
		c[++l1] = u, u = a[u].fa;
	}
	c[++l1] = 1;
	int l2 = 0;
	while (v != 1)
	{
		d[++l2] = v, v = a[v].fa;
	}
	d[++l2] = 1;
	int x = 0;
	for (int i = l1, j = l2; i && j; --i, --j)
	{
		if (c[i] == d[j])
		{
			x = c[i];
		}
		else
		{
			break;
		}
	}
	std::cout << x;
	return 0;
}

优化方法

  1. 先让两个结点的深度相同。
    1. 预处理出每个结点的深度。
    2. 即让深度更高的那个结点往上爬到跟另一个节点同一层。
  2. 两个节点一起向上爬，显然同一层如果相遇就是最近公共祖先。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 500000 + 10;

struct Node
{
	int depth;
	int l, r, fa;
} a[N];

int n;
int q[N];

void setDepth()
{
	int front = 1, rear = 1;
	while (front <= rear)
	{
		int p = q[front];
		++front;
		if (a[p].l)
			q[++rear] = a[p].l, a[a[p].l].depth = a[p].depth + 1;
		if (a[p].r)
			q[++rear] = a[p].r, a[a[p].r].depth = a[p].depth + 1;
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n ;
	for (int i = 1; i <= n; i++)
	{
		int x, y;
		std::cin >> x >> y;
		if (x)
			a[i].l = x, a[x].fa = i;
		if (y)
			a[i].r = y, a[y].fa = i;
	}
	setDepth();
	int u, v;
	std::cin >> u >> v;
	if (a[u].depth < a[v].depth)
	{
		std::swap(u, v);
	}
	int x = a[u].depth - a[v].depth;
	for (int i = 1; i <= x; i++)
	{
		u = a[u].fa;
	}
	while (u != v)
	{
		u = a[u].fa, v = a[v].fa;
	}
	std::cout << u;
	return 0;
}

倍增再优化

让两个结点深度相等的操作以及一起向上爬的操作都是一步步爬的，显然可以用倍增优化。

一切的一切，先预处理出各个数的 \(\lg\) 。

for (int i = 1; i <= n; ++i)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);

预处理一个倍增数组 fa，第一维存结点，第二维存 \(2\) 的幂次方的幂，那么一个结点的 \(2^n\) 祖先可以等同于 一个节点的 \(2^{n - 1}\) 祖先的 \(2^{n - 1}\) 的祖先。

for (int i = 1; i <= lg[depth[now]]; ++i)
	fa[now][i] = fa[fa[now][i - 1]][i - 1];

之后的相关操作都可以用该数组优化。

int LCA(int x, int y)
{
	if (depth[x] < depth[y])
		swap(x, y);
	while (depth[x] > depth[y])
		x = fa[x][lg[depth[x] - depth[y]] - 1];
	if (x == y)
		return x;
	for (int k = lg[depth[x]] - 1; k >= 0; --k)
	{
		if (fa[x][k] != fa[y][k])
		{
			x = fa[x][k], y = fa[y][k];
		}
	}
	return fa[x][0];
}

P3379 【模板】最近公共祖先 LCA

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Node
{
	int t, nex;
} e[500010 << 1];

int head[500010], tot;

void add(int x, int y)
{
	e[++tot].t = y;
	e[tot].nex = head[x];
	head[x] = tot;
}

int depth[500001], fa[500001][22], lg[500001];

void dfs(int now, int father)
{
	fa[now][0] = father;
	depth[now] = depth[father] + 1;
	for (int i = 1; i <= lg[depth[now]]; ++i)
		fa[now][i] = fa[fa[now][i - 1]][i - 1];
	for (int i = head[now]; i; i = e[i].nex)
		if (e[i].t != father)
			dfs(e[i].t, now);
}

int LCA(int x, int y)
{
	if (depth[x] < depth[y])
		swap(x, y);
	while (depth[x] > depth[y])
		x = fa[x][lg[depth[x] - depth[y]] - 1];
	if (x == y)
		return x;
	for (int k = lg[depth[x]] - 1; k >= 0; --k)
	{
		if (fa[x][k] != fa[y][k])
		{
			x = fa[x][k], y = fa[y][k];
		}
	}
	return fa[x][0];
}

int main()
{
	int n, m, s;
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n - 1; ++i)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
	for (int i = 1; i <= n; ++i)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	dfs(s, 0);
	for (int i = 1; i <= m; ++i)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d\n", LCA(x, y));
	}
	return 0;
}

相关题目

  • P3884 JLOI2009 二叉树问题

  • #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define max(a,b) a > b ? a : b

const int N = 1e2 + 10;
int n;

int tot, head[N], fa[N], depth[N], kt[N];

inline void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

struct Node
{
	int to, next;
} edge[N];

void add(int x, int y)
{
	edge[++tot].to = y;
	edge[tot].next = head[x];
	head[x] = tot;
}

void dfs(int now, int father)
{
	fa[now] = father;
	depth[now] = depth[father] + 1;
	for (int i = head[now]; i; i = edge[i].next)
	{
		if (edge[i].to != father)
		{
			dfs(edge[i].to, now);
		}
	}
}

int getLCA(int x, int y)
{
	if (depth[x] < depth[y])
	{
		swap(x, y);
	}
	int k = depth[x] - depth[y];
	for (int i = 1; i <= k; i++)
	{
		x = fa[x];
	}
	while (x != y)
	{
		x = fa[x], y = fa[y];
	}
	return x;
}

int getDistance(int a, int b)
{
	int temp = getLCA(a, b);
	return (depth[a] - depth[temp]) * 2 + depth[b] - depth[temp];
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n;
	for (int i = 1; i < n; i++)
	{
		int x, y;
		std::cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	int dep = 0;
	dfs(1, 0);
	for (int i = 1; i <= n; i++)
	{
		dep = max(dep, depth[i]);
		kt[depth[i]]++;
	}
	int width = 0;
	for (int i = 1; i <= dep; i++)
	{
		width = max(width, kt[i]);
	}
	int u, v;
	std::cin >> u >> v;
	std::cout << dep << std::endl << width << std::endl << getDistance(u, v);
	return 0;
}