「一本通 4.4 练习 3」聚会

形式化题目

给定一棵 $N$ 个结点、 $N-1$ 条边的树，每条边的权为 1， $d(u,v)$ 表示树上 $u$ 到 $v$ 的唯一路径的边数。每次询问给出三个结点 $a, b, c$ ，要求选出一个结点 $P$ ，使

f(P) = d(P, a) + d(P, b) + d(P, c)

最小，并输出这个 $P$ 与 $f(P)$ 的最小值。由于 $P$ 是三条两两路径的唯一公共点（见下文推导），输出没有歧义。

样例树

下图展示题面样例的 6 个城市与 5 条道路：

graph TD
    1 --- 2
    2 --- 3
    2 --- 4
    4 --- 5
    5 --- 6

以第一次询问 $(4,5,6)$ 为例：三人分别站在 $4,5,6$ ， $5$ 到三人的距离是 $1+0+1=2$ ，任何其他点的距离和都更大，所以输出 5 2；题面四次询问的答案依次是 5 2、2 5、4 1、6 0。

正解

思路

朴素做法。 每次询问枚举全部 $N$ 个候选城市，对每个候选求它到 $a,b,c$ 的距离和取最小：单次要跑 BFS/DFS（或沿父链爬） $O(N)$ ， $M$ 次询问合计 $O(NM)$ 。在 $N = M = 5 \times 10^5$ 时约 $2.5 \times 10^{11}$ 次运算，显然超时。朴素做法暴露的瓶颈是：距离和最优点都是"路径"上的量，却每次现算——而树上两点路径唯一，完全可以预先结构化。

第一步：把目标函数拆成两两距离。 对任意结点 $v$ ，把三组"到两点距离和"相加：

2f(v) = [d(v,a)+d(v,b)] + [d(v,b)+d(v,c)] + [d(v,c)+d(v,a)] \geqslant d(a,b)+d(b,c)+d(c,a)

每组用到路径上的三角不等式：设 $d(v,\mathrm{path}(u,w))$ 表示 $v$ 到这条路径的最短距离，则 $d(v,u)+d(v,w) = d(u,w) + 2\,d(v,\mathrm{path}(u,w)) \geqslant d(u,w)$ ，取等当且仅当 $v$ 就在 $\mathrm{path}(u,w)$ 上。于是得到下界

f(v) \geqslant \tfrac12\big(d(a,b)+d(b,c)+d(c,a)\big)

且 $v$ 取到下界 $\iff v$ 同时位于 $\mathrm{path}(a,b)$ 、 $\mathrm{path}(b,c)$ 、 $\mathrm{path}(c,a)$ 三条路径上。

第二步：三条路径的公共点存在且唯一，它就是三对 LCA 中最深的那个。

存在：记 $x = \mathrm{lca}(a,b)$ 、 $y = \mathrm{lca}(b,c)$ 、 $z = \mathrm{lca}(c,a)$ ，三者两两可比（例如 $x,z$ 都是 $a$ 的祖先）。不妨设 $x$ 最深，则 $\mathrm{dep}(x) \geqslant \mathrm{dep}(z)$ 说明 $x$ 在 $a \to z$ 的祖先链上，故 $x \in \mathrm{path}(a,c)$ ；同理 $x \in \mathrm{path}(b,c)$ ；而 $x \in \mathrm{path}(a,b)$ 由定义显然。三条路径交集非空，下界可达。
唯一：在 $\mathrm{path}(a,b)$ 上 $d(v,a)+d(v,b) = d(a,b)$ 恒成立，故 $f(v) = d(a,b) + d(v,c)$ 。记 $w$ 为从 $c$ 通向 $a$ 、通向 $b$ 两条路径的分岔点：它们先重合（ $c \to w$ ）再分开、分别走向 $a$ 与 $b$ ，所以 $w$ 落在 $\mathrm{path}(a,b)$ 上，且 $c$ 到链上任何一点都要经过 $w$ ——于是对链上任意 $v$ 有 $d(v,c) = d(v,w) + d(w,c)$ ，而 $d(v,w)$ 沿链就是位置差，严格 V 形。因此 $\mathrm{path}(a,b)$ 上 $f$ 的最小点唯一（恰为 $w$ ）。三路交集含于 $\mathrm{path}(a,b)$ 且其中每点都取到全局下界，故交集只有这一个点；前一条已证最深 LCA 在交集里，所以它就是 $w$ 。

同深度的两个 LCA 必为同一点（两两可比，可比且同深度即相等），所以"取最深"不会出现并列歧义。

第三步：费用也只用三个 LCA。 树上距离公式 $d(u,v) = \mathrm{dep}(u)+\mathrm{dep}(v)-2\,\mathrm{dep}(\mathrm{lca}(u,v))$ 代入第一步的下界，相同项抵消：

C = \mathrm{dep}(a)+\mathrm{dep}(b)+\mathrm{dep}(c) - \mathrm{dep}(x) - \mathrm{dep}(y) - \mathrm{dep}(z)

于是每次询问只需 3 次 LCA：聚会点 $P$ 取三对 LCA 中最深的，费用 $C$ 用上面的深度和公式。

第四步：LCA 用重链剖分。 倍增要 $O(N \log N)$ 的祖先表，在 Python 里 $5 \times 10^5$ 规模下内存偏重；重链剖分只用几个 $O(N)$ 数组：把"重儿子连成的链"压在一起，查询时若两点链顶不同，就把链顶更深的整条链整体上移到父链——每跨一条轻边，所在子树大小至少减半，因此最多跳 $O(\log N)$ 次；两点同链时浅者即 LCA。实现里根的父点记为 0（城市编号从 1 开始），下标 0 不参与任何查询。

下表把样例 4 次聚会逐对拆开，验证"最深 LCA 即聚会点"与费用公式（根取 $1$ ）：

#	$(a,b,c)$	$\mathrm{lca}(a,b)$	$\mathrm{lca}(b,c)$	$\mathrm{lca}(c,a)$	最深 LCA $=P$	深度和公式算出 $C$
1	4 5 6	4 (深 2)	5 (深 3)	4 (深 2)	5	2
2	6 3 1	2 (深 1)	1 (深 0)	1 (深 0)	2	5
3	2 4 4	2 (深 1)	4 (深 2)	2 (深 1)	4	1
4	6 6 6	6 (深 4)	6 (深 4)	6 (深 4)	6	0

表中每次的最深 LCA 与标准输出的 $P$ 完全一致，费用列也逐行对上样例输出。第 1 行三条路径交在 $5$ 、第 2 行交在 $2$ ，都可对着上面的树逐条描一遍。第 3 行两个 $4$ 重合，三对 LCA 中 $\mathrm{lca}(b,c)=4$ 最深，聚会点取在人数多的那一侧；第 4 行三点相同，三对 LCA 全相等，费用为 $0$ ——这正是"同深度必为同点、取最深没有歧义"的直观例子。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 18:04
# update_at: 2026-09-30 18:19

import sys


def build_chains(n: int, adj: list[list[int]], root: int = 1) -> tuple[list[int], list[int], list[int]]:
    """预处理树：返回父表 parent、深度表 depth 和重链顶表 head，供 O(log n) 求 LCA。"""
    parent = [0] * (n + 1)
    depth = [0] * (n + 1)
    order = [root]
    for u in order:                                # 列表边长边迭代，等价于先根遍历整棵树
        for v in adj[u]:
            if v != parent[u]:                     # 邻居里只有父点需要避开
                parent[v] = u
                depth[v] = depth[u] + 1
                order.append(v)

    size = [1] * (n + 1)
    for u in reversed(order):                      # 反向先根序 = 后根序，子树先于父点结算
        size[parent[u]] += size[u]                 # 根的 parent 是 0，下标 0 不会被查询

    head = [0] * (n + 1)
    heavy = [0] * (n + 1)
    for u in order:                                # 正向先根序，父点的 heavy 此时已就绪
        p = parent[u]
        head[u] = head[p] if heavy[p] == u else u  # 是父点的重儿子就共用链顶，否则自成链顶
        for v in adj[u]:
            if v != p and (heavy[u] == 0 or size[v] > size[heavy[u]]):
                heavy[u] = v                       # 最大子树即重儿子，轻边每次跨越都让子树至少减半
    return parent, depth, head


def query_lca(u: int, v: int, depth: list[int], parent: list[int], head: list[int]) -> int:
    """重链跳跃求 LCA：每次把链顶更深的那条链整体上移到父链，同链时浅者即答案。"""
    while head[u] != head[v]:
        if depth[head[u]] < depth[head[v]]:
            u, v = v, u
        u = parent[head[u]]
    return u if depth[u] < depth[v] else v


def meeting(a: int, b: int, c: int, depth: list[int], parent: list[int], head: list[int]) -> tuple[int, int]:
    """一次聚会：返回费用最小的聚会点 P 与最小总费用 C，三对 LCA 一次问齐。"""
    ab, bc, ca = (query_lca(u, v, depth, parent, head) for u, v in ((a, b), (b, c), (c, a)))

    # 聚会点 = 三条两两路径的唯一公共点 = 三对 LCA 中最深的那个（同深度必为同点）
    p = ab
    if depth[bc] > depth[p]:
        p = bc
    if depth[ca] > depth[p]:
        p = ca

    # 最小费用 = 两两距离和 ÷ 2 = 三点深度和 − 三个 LCA 深度和
    return p, depth[a] + depth[b] + depth[c] - depth[ab] - depth[bc] - depth[ca]


def solve() -> None:
    data = (int(t) for line in sys.stdin.buffer for t in line.split())  # 逐行惰性读入，5×10^5 行不整份驻留内存
    n, m = next(data), next(data)

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = next(data), next(data)
        adj[a].append(b)
        adj[b].append(a)

    parent, depth, head = build_chains(n, adj)

    out: list[str] = []
    for _ in range(m):
        a, b, c = next(data), next(data), next(data)
        out.append("%d %d" % meeting(a, b, c, depth, parent, head))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:10
 * update_at: 2026-10-05 08:10
 */
// main.cpp：三人聚会点 = path(a,b)、path(b,c)、path(c,a) 的唯一公共点，
// 即三对 LCA 中最深的那个；最小费用 = 三点深度和 − 三个 LCA 深度和。
// LCA 用重链剖分：O(N) 预处理，每次询问 3 次 O(log N) 跳跃。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005; // 城市数上限 5*10^5

int n, m;
// 链式前向星存树：无向边两条，2*(N-1) 条有向边
int head[MAXN], nxt[2 * MAXN], to[2 * MAXN], edge_cnt;

int parent[MAXN]; // parent[u] = u 的父点，根的父点记 0（城市编号从 1 开始）
int depth[MAXN];  // depth[u] = u 到根的边数
int sz[MAXN];     // sz[u] = u 的子树大小
int heavy_son[MAXN]; // heavy_son[u] = u 的重儿子（子树最大），没有儿子为 0
int chain_top[MAXN]; // chain_top[u] = u 所在重链的链顶

// 加一条 u -> v 的有向边。
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 第一遍预处理：非递归先序遍历求 parent、depth，再倒序累加 sz、选重儿子、定链顶
// （用手工栈模拟，防止 5*10^5 的链形树把递归栈压爆）
void dfs_build(int root) {
    static int stk[MAXN];   // 手工栈
    static int order[MAXN]; // order[1..cnt] 保存先序遍历序，儿子一定排在父亲后面
    int cnt = 0;

    // 先序遍历：顺路定 parent 和 depth
    int tp = 0;
    stk[++tp] = root;
    parent[root] = 0;
    depth[root] = 0;
    while (tp > 0) {
        int u = stk[tp];
        tp--;
        cnt++;
        order[cnt] = u;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == parent[u]) continue; // 邻居里只有父点要避开
            parent[v] = u;
            depth[v] = depth[u] + 1;
            stk[++tp] = v;
        }
    }

    // 倒先序累加子树大小：结点先于父点被结算
    for (int u = 1; u <= n; u++) sz[u] = 1;
    for (int i = cnt; i >= 1; i--) {
        int u = order[i];
        sz[parent[u]] += sz[u];
    }

    // 求重儿子：每个点选子树最大的儿子
    for (int u = 1; u <= n; u++) {
        heavy_son[u] = 0;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == parent[u]) continue;
            if (heavy_son[u] == 0 || sz[v] > sz[heavy_son[u]]) {
                heavy_son[u] = v;
            }
        }
    }

    // 定链顶：父点先序在前，顺序扫描 order 即可
    chain_top[root] = root;
    for (int i = 1; i <= cnt; i++) {
        int u = order[i];
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int w = to[e];
            if (w == parent[u]) continue;
            if (w == heavy_son[u]) chain_top[w] = chain_top[u]; // 重儿子共用链顶
            else chain_top[w] = w;                              // 轻儿子自成链顶
        }
    }
}

// 重链跳跃求 LCA：每次把链顶更深的那条链整体上移到父链，同链时浅者即答案。
int query_lca(int u, int v) {
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] < depth[chain_top[v]]) {
            int t = u; u = v; v = t; // 保证 u 所在链顶更深
        }
        u = parent[chain_top[u]]; // 整条链跳到父链
    }
    if (depth[u] < depth[v]) return u;
    return v;
}

// 一次聚会：返回费用最小的聚会点 P 与最小总费用 C。
void query_meeting(int a, int b, int c, int &p, ll &cost) {
    int ab = query_lca(a, b);
    int bc = query_lca(b, c);
    int ca = query_lca(c, a);

    // 聚会点 = 三对 LCA 中最深的那个（同深度必为同一点，无歧义）
    p = ab;
    if (depth[bc] > depth[p]) p = bc;
    if (depth[ca] > depth[p]) p = ca;

    // 最小费用 = d(a,b)+d(b,c)+d(c,a) 除以 2 = 三点深度和 − 三个 LCA 深度和
    cost = (ll)depth[a] + depth[b] + depth[c] - depth[ab] - depth[bc] - depth[ca];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add_edge(a, b);
        add_edge(b, a);
    }
    dfs_build(1);

    for (int i = 1; i <= m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        int p;
        ll cost;
        query_meeting(a, b, c, p, cost);
        printf("%d %lld\n", p, cost);
    }
    return 0;
}

复杂度

时间复杂度：预处理三次线性扫描 $O(N)$ ；每次询问 3 次重链跳跃 LCA，每次 $O(\log N)$ ，合计 $O(N + M \log N)$ ，与倍增 LCA 的标准正解同阶（更小常数）。
空间复杂度： $O(N)$ ，邻接表与 parent / depth / size / heavy / head 各占一线性数组，没有倍增表。
实测（本地 20s/测例、不做内存判定）： $N = M = 5 \times 10^5$ 的两组各约 2.7s、峰值约 145MB，10 组真实数据全部输出一致。

总结

三人聚会问题 = 树上三元中位数：三角不等式给出下界 $\tfrac12\sum d$ ，取等条件把最优点锁定到三条两两路径的公共点。
公共点存在且唯一，恰好是三对 LCA 中最深的那个；费用等于三点深度和减去三对 LCA 深度和，一次询问 3 次 LCA 全部解决。
LCA 用重链剖分落地： $O(N)$ 预处理、 $O(\log N)$ 查询、 $O(N)$ 空间，正是 Python 在 $5 \times 10^5$ 规模下的可行选择。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7三个结点 a, b, c
|- 朴素：枚举每个点求距离和 → O(NM)，超时
`- 树上路径唯一，可以 LCA 化
   |- 下界：2f(v) ≥ d(a,b)+d(b,c)+d(c,a)，取等 ⇔ v 在三条两两路径上
   |- 三路公共点存在且唯一 = 三对 LCA 中最深者 → 聚会点 P
   `- 费用 = 三点深度和 − 三对 LCA 深度和
      `- 重链跳跃 O(log N) 求 LCA → 每次询问 O(log N)

先看每个节点代表的推理结论：下界解释"为什么只需看三条路径的交点"，唯一性解释"为什么输出确定"，最后两行说明交点与费用如何被 3 次 LCA 表出。图中只保留正文已证明的关键关系，样例的具体数字见上文推导表。