【题解】LuoGu4281：[AHOI2008]紧急集合 / 聚会

本文介绍了一种利用LCA（最近公共祖先）算法解决树状结构中三点最优集合位置及其路径长度的问题。通过倍增法预处理每个节点的深度与祖先信息，快速计算任意两点间的LCA，并据此确定三个点的最佳会合点，最终计算出从各点到该会合点的总路径长度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
这题挺简单
首先，任意三个点可以有一个通式，看下图
在这里插入图片描述
假设我们现在询问1 2 3三点
发现它们走到4这个点是最优的，而4又是1与2的lca
找找4这个点有什么性质
$l c a (1, 2) = 4, l c a (1, 3) = 5, l c a (2, 3) = 5$
发现三点任意两点的lca有两个是重复的，而那个不重复的lca正是它们的集合地点

问题1已经解决，现在让我们算算总路程
lca用倍增解决，然后我们可以得到每个点的深度
来一波推导： $ANS=d_1-d_4+d_2-d_4+d_3-d_5+d_4-d_5=d_1+d_2+d_3-d_4-d_5-d_5$
可以看成三个点深度之和减去三个lca深度之和
这道题就这么愉快地被我们解决啦

Code：

#include <bits/stdc++.h>
#define maxn 500010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], d[maxn], fa[maxn][25], n, m;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge){ y, head[x] }; head[x] = num; }

void dfs(int u, int pre){
	d[u] = d[pre] + 1, fa[u][0] = pre;
	for (int i = 0; fa[u][i]; ++i) fa[u][i + 1] = fa[fa[u][i]][i];
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs(v, u);
	}
}

int lca(int u, int v){
	if (d[u] > d[v]) swap(u, v);
	for (int i = 20; i >= 0; --i) if (d[u] <= d[fa[v][i]]) v = fa[v][i];
	if (u == v) return u;
	for (int i = 20; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

int main(){
	n = read(), m = read();
	for (int i = 1; i < n; ++i) {
		int x = read(), y = read();
		addedge(x, y); addedge(y, x);
	}
	dfs(1, 0);
	while (m--){
		int x = read(), y = read(), z = read(), ans = d[x] + d[y] + d[z];
		int lca1 = lca(x, y), lca2 = lca(x, z), lca3 = lca(y, z);
		ans -= d[lca1] + d[lca2] + d[lca3];
		if (lca1 == lca2) printf("%d %d\n", lca3, ans); else
		if (lca1 == lca3) printf("%d %d\n", lca2, ans); else printf("%d %d\n", lca1, ans);
	}
	return 0;
}