P4281 [AHOI2008] 紧急集合 / 聚会

SunnyYuan的博客 / 2024-08-09 / 原文

题意

给出 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;
}