会议 - 题目列表

形式化题目

给定一棵 $n$ 个点、 $n-1$ 条边的无向树，每条边长度都是 $1$ 。对每个点 $x$ ，记

S(x) = \sum_{u=1}^{n} \mathrm{dist}(u, x)

即所有点到 $x$ 的距离和。要求找出使 $S(x)$ 最小的点，输出它的编号与 $S(x)$ ；若有多个点同样最小，输出编号最小的那个。

暴力

先看一个可以直接验证想法的朴素解：

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/**
 * 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-08-12 22:27
 * update_at: 2026-08-12 22:27
 */
// brute.cpp：小数据暴力解，枚举每个点作为会议地点，再 BFS 计算距离和。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

int n;
vector<int> g[MAXN]; // 树的邻接表

// 以 start 为会议地点做一次 BFS，返回所有点到它的距离和。
long long calc_sum_from(int start) {
    static int dist[MAXN]; // dist[u]：start 到 u 的距离，-1 表示尚未访问
    for (int i = 1; i <= n; i++) dist[i] = -1;

    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }

    long long sum = 0;
    for (int i = 1; i <= n; i++) sum += dist[i];
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 枚举每个点作为会议地点；距离和更小才更新，相等时保留编号小者。
    int best_node = 1;
    long long best_sum = calc_sum_from(1);
    for (int i = 2; i <= n; i++) {
        long long now = calc_sum_from(i);
        if (now < best_sum) {
            best_sum = now;
            best_node = i;
        }
    }

    cout << best_node << " " << best_sum << "\n";

    return 0;
}

brute.cpp 枚举每个点作为会议地点，对每个点各做一次 BFS 求距离和，复杂度 $O(n^2)$ ，无法通过 $n = 5 \times 10^4$ 。

思路

本题有两种解法，正式主解是解法一（重心判定，main.cpp），它依赖一条数学性质；解法二（换根 DP，main-bfs-dp.cpp 与 main-dfs-dp.cpp） 是更通用的树形 DP 套路，不依赖该性质也能求出答案。两个解法的复杂度都是 $O(n)$ 。

解法一：重心判定

思路

关键观察：距离和最小的点就是树的重心。先证明这个结论——相邻两点换根时，距离和可以 $O(1)$ 转移。设 $v$ 是 $u$ 的儿子，把树以 $1$ 为根，会议地点从 $u$ 移到 $v$ 。对树中的任意点 $x$ ， $x$ 到 $v$ 与 $x$ 到 $u$ 的距离之差，由 $x$ 是否在 $v$ 的子树内决定：

$x$ 在 $v$ 子树内（共 $\mathrm{subtree\_size}[v]$ 个点）： $x$ 到 $u$ 的路径先到 $v$ 再经过边 $(v,u)$ ，移到 $v$ 后省掉这条边，距离减少 $1$ ，即 $\mathrm{dist}(x,v) = \mathrm{dist}(x,u) - 1$ ；
$x$ 不在 $v$ 子树内（共 $n - \mathrm{subtree\_size}[v]$ 个点）： $x$ 到 $v$ 的路径要绕道 $u$ 再经边 $(u,v)$ ，距离增加 $1$ ，即 $\mathrm{dist}(x,v) = \mathrm{dist}(x,u) + 1$ 。

把每个点的新距离代入 $S(v)$ （记 $S(v)$ 为"会议地点定在 $v$ 时所有点到 $v$ 的距离和"，即形式化题目中的 $S(x)$ 取 $x = v$ ），按这两组分别求和：

S(v) = \sum_{x \in \text{v子树}} \big(\mathrm{dist}(x,u) - 1\big) + \sum_{x \notin \text{v子树}} \big(\mathrm{dist}(x,u) + 1\big)

第一组有 $\mathrm{subtree\_size}[v]$ 项各减 $1$ ，第二组有 $n - \mathrm{subtree\_size}[v]$ 项各加 $1$ ，所以：

S(v) = S(u) - \mathrm{subtree\_size}[v] + \big(n - \mathrm{subtree\_size}[v]\big) = S(u) + n - 2 \cdot \mathrm{subtree\_size}[v]

这就是换根公式 $\mathrm{dist\_sum}[v] = \mathrm{dist\_sum}[u] + n - 2 \cdot \mathrm{subtree\_size}[v]$ ：它把"重新算一遍 $S(v)$ “化简成"在 $S(u)$ 上做一次由子树规模差驱动的增量修正”。

换根公式中， $S(u) \to S(v)$ 这个方向上的变化量是 $n - 2 \cdot \mathrm{subtree\_size}[v]$ ，它的符号决定沿这条边移动值会不会变好：

若 $\mathrm{subtree\_size}[v] > n/2$ ，变化量为负，移到 $v$ 会减小距离和；
若 $\mathrm{subtree\_size}[v] < n/2$ ，变化量为正，移到 $v$ 会增大距离和；
若恰好等于 $n/2$ ，变化量为零，移到 $v$ 距离和不变。

因此距离和最小的点正是删掉它后所有连通块大小都不超过 $n/2$ 的重心——"距离和最小"与"最大连通块 ≤ n/2"是同一组点的两种刻画。

于是只需两步：用重心模板求出所有重心（重心至多两个且相邻，两个重心距离和相同，取编号最小者），再对选中的点做一次 BFS 求距离和。

代码

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/**
 * 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-08-12 22:27
 * update_at: 2026-08-16 00:10
 */
// main.cpp：距离和最小的点 = 树的重心（P1395 会议）。
// 用 rbook 模板 tree-centroid2 求出所有重心，取编号最小者（多重心时距离和相同），
// 再一遍 BFS 求它的距离和。
#include <bits/stdc++.h>
using namespace std;

using Graph = std::vector<std::vector<int>>;
Graph tree;  // 全局邻接表：使用前先 resize(n+1) 并加边

// 求树的所有重心。
// 重心：删除该点后，剩下的每个连通块大小都不超过 n/2。
// 与 tree_centroid.cpp 不同：不维护全局最小值，直接按"最大连通块 ≤ n/2"判定重心。
struct TreeCentroid2 {
    int n;
    std::vector<int> sz;   // sz[u] = u 的子树大小
    std::vector<int> ans;  // 答案：所有重心，按编号升序

    explicit TreeCentroid2(int n) : n(n), sz(n + 1) {}

    // 返回所有重心（编号升序）
    std::vector<int> find_centroids(int root = 1) {
        ans.clear();
        dfs(root, 0);
        std::sort(ans.begin(), ans.end());
        return ans;
    }

    // 统计子树大小；若 B(u) = 删除 u 后最大的连通块大小 ≤ n/2，u 就是重心
    void dfs(int u, int parent) {
        sz[u] = 1;
        int mx = 0;  // B(u)：先看各儿子子树

        for (int v : tree[u]) {
            if (v == parent) continue;
            dfs(v, u);
            sz[u] += sz[v];
            mx = std::max(mx, sz[v]);
        }

        // 父亲方向也是一块：整棵树减去 u 的子树
        mx = std::max(mx, n - sz[u]);

        // 等价判定：B(u) ≤ n/2 ⟺ u 是重心
        if (mx <= n / 2) ans.push_back(u);
    }
};

// 从 s 出发 BFS，返回所有点到 s 的距离和（s 本身的深度 0 不计入）。
long long dist_sum_from(int s) {
    queue<int> q;
    vector<int> dist(tree.size(), -1);
    dist[s] = 0;
    q.push(s);
    long long total = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : tree[u]) {
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + 1;
            total += dist[v];
            q.push(v);
        }
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    tree.resize(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // 距离和最小的点 = 重心；重心至多两个且相邻、距离和相同，取编号最小的。
    TreeCentroid2 tc(n);
    vector<int> cs = tc.find_centroids();
    int meeting = cs[0];

    cout << meeting << ' ' << dist_sum_from(meeting) << '\n';
    return 0;
}

复杂度

时间：求重心 DFS 一次 $O(n)$ ，求距离和 BFS 一次 $O(n)$ ，总 $O(n)$ 。
空间：邻接表与子树大小数组 $O(n)$ 。

解法二：换根 DP

思路

不利用重心定理，把每个点的距离和全部算出来再扫描取最小，属于通用的"树形 DP + 换根"套路。先把树以 $1$ 为根，用 BFS 求出遍历序、父亲、深度，顺带得到 dist_sum[1]（等于所有点的深度之和）；逆序遍历序累加子树大小 subtree_size；再正序遍历序，用解法一推导出的换根公式 dist_sum[v] = dist_sum[u] + n - 2 * subtree_size[v]（沿父子边移动时， $v$ 子树内 $sz[v]$ 个点距离各 $-1$ 、其余点各 $+1$ ）沿父子边递推全部点的距离和。

以样例链 $1 - 2 - 3 - 4$ 为例，以 $1$ 为根做一次换根 DP。先画出这棵树，括号里标出每个点的子树大小（以 $1$ 为根）：

text

1
2
3
4
5
6
7        1 (sz=4)
        |
        2 (sz=3)
        |
        3 (sz=2)
        |
        4 (sz=1)

从根 $1$ 往下看，这棵树是一根链：每个点的子树就是它自己加上它下方的所有点，所以 sz 沿根向叶子递减 $4,3,2,1$ 。换根 DP 从根出发逐层往下递推： $1 \to 2 \to 3 \to 4$ ，每步都只跨一条边。

换根 DP 得到的结果如下：

节点 $u$	1	2	3	4
$\mathrm{subtree\_size}[u]$	4	3	2	1
$\mathrm{dist\_sum}[u]$	6	4	4	6

先看 subtree_size 一行：叶子 $4$ 是 $1$ ，向上累加得到 $3$ 、 $2$ 、 $4$ 。再看 dist_sum 一行：dist_sum[1] = 0+1+2+3 = 6，然后 $\mathrm{dist\_sum}[2] = 6 + 4 - 2\times3 = 4$ ， $\mathrm{dist\_sum}[3] = 4 + 4 - 2\times2 = 4$ ， $\mathrm{dist\_sum}[4] = 4 + 4 - 2\times1 = 6$ 。节点 $2$ 与 $3$ 距离和同为 $4$ ，取编号小的 $2$ ，与样例输出 2 4 一致。

代码

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/**
 * 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-08-12 22:27
 * update_at: 2026-08-12 22:27
 */
// main-bfs-dp.cpp：换根 DP 求树上所有点到某点的距离和最小值（P1395 会议）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

int n;
vector<int> g[MAXN];      // 树的邻接表
int parent_node[MAXN];    // parent_node[u]：以 1 为根时 u 的父亲，根的父节点为 0
int depth_arr[MAXN];      // depth_arr[u]：以 1 为根时 u 的深度
int order_arr[MAXN];      // order_arr[]：BFS 遍历序，第 1 个是根 1
int order_cnt;            // BFS 访问到的节点个数
int subtree_size[MAXN];   // subtree_size[u]：以 1 为根时 u 子树内的节点数
long long dist_sum[MAXN]; // dist_sum[u]：所有节点到 u 的距离和

// BFS 求遍历序、父亲、深度，并顺带求 dist_sum[1]（所有点深度之和）。
void bfs_root() {
    queue<int> q;
    q.push(1);
    parent_node[1] = 0;
    depth_arr[1] = 0;
    order_cnt = 0;
    dist_sum[1] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order_arr[++order_cnt] = u;
        dist_sum[1] += depth_arr[u];

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent_node[u]) continue;
            parent_node[v] = u;
            depth_arr[v] = depth_arr[u] + 1;
            q.push(v);
        }
    }
}

// 逆序遍历序，自底向上累加每棵子树的大小。
void calc_subtree_size() {
    for (int i = 1; i <= n; i++) subtree_size[i] = 1;
    for (int i = order_cnt; i >= 1; i--) {
        int u = order_arr[i];
        if (parent_node[u] != 0) {
            subtree_size[parent_node[u]] += subtree_size[u];
        }
    }
}

// 换根 DP：根从 u 移到儿子 v 时，用公式推出 v 的距离和。
void reroot_dp() {
    for (int i = 1; i <= order_cnt; i++) {
        int u = order_arr[i];
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (parent_node[v] != u) continue; // 只走父亲 -> 儿子方向

            // 换根公式：v 子树内 subtree_size[v] 个点距离各 -1，
            // 其余 n - subtree_size[v] 个点距离各 +1，
            // 所以 dist_sum[v] = dist_sum[u] + n - 2 * subtree_size[v]。
            dist_sum[v] = dist_sum[u] + (long long)n - 2LL * subtree_size[v];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    bfs_root();
    calc_subtree_size();
    reroot_dp();

    // 距离和取最小；距离和相等时保留编号最小的点（只严格小于才更新）。
    int best_node = 1;
    long long best_sum = dist_sum[1];
    for (int i = 2; i <= n; i++) {
        if (dist_sum[i] < best_sum) {
            best_sum = dist_sum[i];
            best_node = i;
        }
    }

    cout << best_node << " " << best_sum << "\n";

    return 0;
}

上面的 BFS 版本用遍历序迭代完成三步；换根 DP 也可以写成两次 DFS 的版本，更贴近手写递归习惯：第一次 DFS 回溯时累加子树大小、向下时累加深度顺带求出 dist_sum[1]，第二次 DFS 从根向叶子用换根公式递推所有点的距离和。

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/**
 * 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-08-16 00:40
 * update_at: 2026-08-16 00:40
 */
// main-dfs-dp.cpp：换根 DP 的两次 DFS 实现（P1395 会议）。
// 第一次 DFS 求子树大小与 dist_sum[1]（所有点深度之和），
// 第二次 DFS 沿父子边用换根公式递推全部点的距离和。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

int n;
vector<int> g[MAXN];      // 树的邻接表
int subtree_size[MAXN];   // subtree_size[u]：以 1 为根时 u 子树内的节点数
long long dist_sum[MAXN]; // dist_sum[u]：所有节点到 u 的距离和

// 第一次 DFS：求子树大小，并累加深度得到 dist_sum[1]。
// dep 表示 u 的深度，根 1 的深度为 0。
void dfs_subtree(int u, int fa, int dep) {
    subtree_size[u] = 1;
    dist_sum[1] += dep;

    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) continue;
        dfs_subtree(v, u, dep + 1);
        subtree_size[u] += subtree_size[v];
    }
}

// 第二次 DFS：换根递推，从 u 移到儿子 v 时用公式推 dist_sum[v]。
void dfs_reroot(int u, int fa) {
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) continue;

        // 换根公式：v 子树内 subtree_size[v] 个点距离各 -1，
        // 其余 n - subtree_size[v] 个点距离各 +1。
        dist_sum[v] = dist_sum[u] + (long long)n - 2LL * subtree_size[v];
        dfs_reroot(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs_subtree(1, 0, 0);
    dfs_reroot(1, 0);

    // 距离和取最小；距离和相等时保留编号最小的点（只严格小于才更新）。
    int best_node = 1;
    long long best_sum = dist_sum[1];
    for (int i = 2; i <= n; i++) {
        if (dist_sum[i] < best_sum) {
            best_sum = dist_sum[i];
            best_node = i;
        }
    }

    cout << best_node << " " << best_sum << "\n";

    return 0;
}

复杂度

时间：BFS、求子树大小、换根 DP、扫描答案各 $O(n)$ ，总 $O(n)$ 。
空间：邻接表与四个 $O(n)$ 数组，总 $O(n)$ 。

复杂度对比

	解法一（重心判定）	解法二（换根 DP）
时间复杂度	$O(n)$	$O(n)$
空间复杂度	$O(n)$	$O(n)$
依赖性质	距离和最小 = 重心	无（通用套路）
额外步骤	求重心 + 一次 BFS 算距离和	递推全部点的距离和 + 扫描取最小
代码量	更短（模板化）	略长

总结

“树上所有点到某点距离和"这类问题有两个方向：一是利用"距离和最小的点就是树的重心"这条性质，直接按重心定义（每个连通块 ≤ n/2）求点；二是通用套路——先以任意点为根求出子树大小，再用换根公式 dist_sum[v] = dist_sum[u] + n - 2 * subtree_size[v] 沿树边递推。难点只在把"重新算一棵树"化简成"相邻两棵子树规模差驱动的增量转移”。rbook 的《树的中心》讲的是另一个目标（到所有点最大距离最小），注意不要混淆。

图示解析

这张 ASCII 图展示整道题的两种解法路线：