题意
给出 3 个点,选出一个点使得 3 个点到这个点的距离之和最小。
思路
- 三个点可以先取 2 个点的 lca,然后与第 3 个点再取 lca。
- 三个点的两两求 lca,至多只会有 2 个不同的结点。
- 三个点的距离 \(dis[x] + dis[y] + dis[z] - dis[lca(a, b)] - dis[lca(b, c)] - dis[lca(a, b)]\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
struct edge {
int to, next;
} e[N * 2];
int head[N], idx = 1;
void add(int u, int v) {
idx++, e[idx].to = v, e[idx].next = head[u], head[u] = idx;
}
int fa[20][N], dep[N];
int n, q;
void dfs(int u, int f) {
fa[0][u] = f;
dep[u] = dep[f] + 1;
for (int i = head[u]; i; i = e[i].next) {
int to = e[i].to;
if (to == f) continue;
dfs(to, u);
}
}
void initf() {
for (int j = 1; j < 20; j++) {
for (int i = 1; i <= n; i++) {
fa[j][i] = fa[j - 1][fa[j - 1][i]];
}
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
if (dep[fa[i][u]] >= dep[v]) u = fa[i][u];
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (fa[i][u]!= fa[i][v]) u = fa[i][u], v = fa[i][v];
}
return fa[0][u];
}
int dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v), add(v, u);
}
dfs(1, 0);
initf();
while (q--) {
int u, v, w;
cin >> u >> v >> w;
int l1 = lca(u, v), l2 = lca(u, w), l3 = lca(v, w);
int ans1, ans2;
if (l1 == l2) ans1 = l3;
else if (l1 == l3) ans1 = l2;
else ans1 = l1;
ans2 = dep[u] + dep[v] + dep[w] - dep[l1] - dep[l2] - dep[l3];
cout << ans1 << ' ' << ans2 << '\n';
}
return 0;
}
标签:idx,fa,int,AHOI2008,紧急集合,dep,P4281,lca,dis
From: https://www.cnblogs.com/Yuan-Jiawei/p/18350322