【题解】P4281 [AHOI2008]紧急集合

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

给出\(n(1\le n \le 5\times 10^5)\)个点和\(n-1\)条连着它们的路径，每一条道路都连接某两个点，且通过这些道路可以走遍所有的点。

有\(m(1 \le m \le 10^5)\)组人分散在这些点上，每组有三个人。给出每组中三人的初始位置。每组确定一个位置使每组内三人到这个点的距离和最小，输出这个距离和。

分析

题目要求得出三个点走到同一个点，所要求的最小花费，可以对这三个点两两求出\(\text{LCA}\)，这三个\(\text{LCA}\)中有二者重合，所以最后最优点只有两个选择。因为在选择不重和的公共点的情况下，一个单独的点移动比另外两个移动距离多（不重的深度更深），所以集结点应在三个\(\text{LCA}\)中与其它两个不同的点上。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>

const int N = 500005;
using namespace std;
int n, m;
struct node {
    int to, next;
} e[N << 2];
int head[N], tmp;

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

int fa[N][22], dep[N];

int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

void dfs(int x, int f) {
    dep[x] = dep[f] + 1;
    fa[x][0] = f;
    for (int i = head[x]; i; i = e[i].next) {
        int v = e[i].to;
        if (v == f) continue;
        dfs(v, x);
    }
}

void lca_init() {
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= n; j++) {
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
        }
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (dep[fa[x][i]] >= dep[y]) {
            x = fa[x][i];
        }
        if (x == y) return x;
    }
    for (int i = 20; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

inline int dis(int x, int y) {
    int l = lca(x, y);
    return abs(dep[x] - dep[l]) + abs(dep[y] - dep[l]);
}

inline int ddis(int l, int a, int b, int c) {
    return dis(l, a) + dis(l, b) + (l, c);
}

int main() {
    //freopen("a.in","r",stdin);
    n = read(), m = read();
    for (int i = 1; i < n; i++) {
        int a = read(), b = read();
        add(a, b);
        add(b, a);
    }
    dfs(1, 0);
    lca_init();
    while (m--) {
        int x = read(), y = read(), z = read();
        int xy = lca(x, y), xz = lca(x, z), yz = lca(y, z);
        int ans;
        if (xy == yz) ans = xz;
        else if (xy == xz) ans = yz;
        else ans = xy;
        printf("%d %d\n", ans, dep[x] + dep[y] + dep[z] - dep[xz] - dep[xy] - dep[yz]);

    }
    return 0;
}