关于 LCA 的简单记录

最近做了几道 LCA 的题目。所以总结一下。

首先我们来回顾一下倍增求 LCA 的流程吧。

首先是初始化：

• 进行 bfs。
• 处理出每层的深度。
• 处理每个节点的 \(2^k\) 级父亲，方式为一个递推，即为由 \(2^{k-1}\) 级祖先的 \(2^{k - 1}\) 祖先推出 \(2^k\) 级祖先。

然后是每次的查询：

• 把 y 的高度提到和 x 相同。运用向上提 \(2^k\) 级的方法，如果不超过 x 的话就继续提。
• 对于 \(k\) 从高到低尝试，如果 x 和 y 的第 \(2^k\) 级祖先不同的话，那么把这二者同时向上提 \(2^k\) 级，根据二进制分解的知识，我们知道用这种方法能向上提任意的数。那么这会使得二者尽可能向上提，使得二者仅差一步就能相会。
• 那么仅差一步的话，直接返回任意一个的父亲就好了。

简单例题：聚会

Y 岛风景美丽宜人，气候温和，物产丰富。Y 岛上有 \(N\) 个城市，有 \(N-1\) 条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是，小可可通过这些道路可以走遍 \(Y\) 岛的所有城市。神奇的是，乘车经过每条道路所需要的费用都是一样的。小可可，小卡卡和小 YY 经常想聚会，每次聚会，他们都会选择一个城市，使得 3 个人到达这个城市的总费用最小。 由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。

题意概括：3 个点在树上，求使这 3 个点联通的树上最短路径。

解法

这道题简单到飞，我们发现可以仅仅先对 x 和 y 求 lca，然后便可以对于 z 进行分类讨论。

z 的情况分为两大类：

• 是 x 和 y 的 lca 的祖先或者和 x 和 y 的 lca 没有亲辈和子辈关系
• x、 y、 z 的公共 lca 是 x 和 y 的 lca

其中第一种情况的解决方案是，集合地点为 x 和 y 的 lca，然后再计算 z 到 lca 的距离，求总和。

而第二种也分两大类，路径为一条线或者带有一个分叉，即为：

• z 为 x 或者 y 的祖先
• z 既非 x 的祖先也非 y 的祖先

前者的解决方案是，集合地点为 z 点，距离为 x 和 y 的距离。

而带有分叉的情况，即后者，若和 x 的 lca 的深度深于和 y 的，那么集合地点选在和 x 的 lca 处，距离为 x 和 y 的距离加 z 到和 x 的 lca 的距离。反之亦然。

那么代码就容易写出了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

const int maxn = 5e5 + 5;

struct E {
	int nxt, to;
} e[maxn << 1];

int n, p, cnt, head[maxn], t;
int f[maxn][23], d[maxn];
queue<int> q;

void add(int a, int b) {
	e[++ cnt].to = b;
	e[cnt].nxt = head[a];
	head[a] = cnt;
}

void bfs() {
	q.push(1);
	d[1] = 1;
	while(q.size()) {
		int x = q.front();
		q.pop();
		for(int i = head[x]; i; i = e[i].nxt) {
			int y = e[i].to;
			if(d[y]) continue;
			d[y] = d[x] + 1;
			f[y][0] = x;
			for(int j = 1; j <= t; j ++) 
				f[y][j] = f[f[y][j - 1]][j - 1];
			q.push(y);
		}
	}
}

int lca(int x, int y) {
	if(d[x] > d[y]) swap(x, y);
	for(int i = t; i >= 0; i --)
		if(d[f[y][i]] >= d[x])
			y = f[y][i];
	if(x == y) return x;
	for(int i = t; i >= 0; i --)
		if(f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}

int main() {
	scanf("%d%d", &n, &p);
	t = (int) (log(n) / log(2)) + 1;
	for(int i = 1, u, v; i < n; i ++) {
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	bfs();
	for(int i = 1, x, y, z; i <= p; i ++) {
		scanf("%d%d%d", &x, &y, &z);
		int lcaxy = lca(x, y);
		int lcaxyz = lca(lcaxy, z);
		if(lcaxyz != lcaxy && lcaxyz != z) {
			printf("%d %d\n", lcaxy, d[x] + d[y] - d[lcaxy] + d[z] - 2 * d[lcaxyz]);
		} else if(lcaxyz == z) {
			printf("%d %d\n", lcaxy, d[x] + d[y] - d[lcaxy] + d[z] - 2 * d[lcaxyz]);
		} else if (lcaxyz == lcaxy) {
			int lcaxz = lca(x, z), lcayz = lca(y, z);
			if(lcaxz == z || lcayz == z) {
				printf("%d %d\n", z, d[x] + d[y] - 2 * d[lcaxy]);
			} else {
				printf("%d %d\n", d[lcaxz] > d[lcayz] ? lcaxz : lcayz, 
								  d[lcaxz] > d[lcayz] ? d[x] + d[y] - 2 * d[lcaxy] + d[z] - d[lcaxz] : d[x] + d[y] - 2 * d[lcaxy] + d[z] - d[lcayz]);
			}
		}
	}
}

简单例题2：[USACO15DEC] Max Flow P

FJ 给他的牛棚的 \(N\) 个隔间之间安装了 \(N-1\) 根管道，隔间编号从 \(1\) 到 \(N\)。所有隔间都被管道连通了。

FJ 有 \(K\) 条运输牛奶的路线，第 \(i\) 条路线从隔间 \(s_i\) 运输到隔间 \(t_i\)。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

解法

这题是一个典型的树上差分问题。具体来讲是先进行倍增 lca 的处理。然后对于每个点的值进行记录。

采用的是经典的差分思想：通过计算差分数组的前缀和即可推断出原数组。

对于每条线路 \((s_i, t_i)\)，在两端各加上 1 点的权值，在两点的 lca 处减少 1 点权值，在两点的 lca 的父亲节点处减少 1 点的权值。这样就可以在这条路径上增加 1 的权值了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

const int maxn = 5e4 + 5;
int n, k;

struct E {
	int nxt, to;
} e[maxn << 1];

int cnt, head[maxn], f[maxn][23], d[maxn], t, p[maxn];
int ans;
queue<int>	q;

void add(int u, int v) {
	e[++ cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

void bfs() {
	q.push(1);
	d[1] = 1;
	while(q.size()) {
		int x = q.front();
		q.pop();
		for(int i = head[x]; i; i = e[i].nxt) {
			int y = e[i].to;
			if(d[y]) continue;
			d[y] = d[x] + 1;
			f[y][0] = x;
			for(int j = 1; j <= t; j ++) 
				f[y][j] = f[f[y][j - 1]][j - 1];
			q.push(y);
		}
	}
}

int lca(int x, int y) {
	if(d[x] > d[y]) swap(x, y);
	for(int i = t; i >= 0; i --)
		if(d[f[y][i]] >= d[x])
			y = f[y][i];
	if(x == y) return x;
	for(int i = t; i >= 0; i --)
		if(f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}

void calc(int x, int fa) {
	for(int i = head[x]; i; i = e[i].nxt) {
		int y = e[i].to;
		if(y == fa) continue;
		calc(y, x);
		p[x] += p[y];
	}
	ans = max(ans, p[x]);
}

int main() {
	cin >> n >> k;
	t = (int) (log(n) / log(2)) + 1;
	for(int i = 1, x, y; i < n; i ++) {
		cin >> x >> y;
		add(x, y), add(y, x);
	}
	bfs();
	for(int i = 1, a, b; i <= k; i ++) {
		cin >> a >> b;
		p[a] ++, p[b] ++, p[lca(a, b)] --, p[f[lca(a, b)][0]] --;
	}
	calc(1, 0);
	cout << ans << endl;
}