P1395 会议

题目描述

有一个村庄居住着 $n$ 个村民，有 $n-1$ 条路径使得这 $n$ 个村民的家联通，每条路径的长度都为 $1$。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式

第一行，一个数 $n$，表示有 $n$ 个村民。

接下来 $n-1$ 行，每行两个数字 $a$ 和 $b$，表示村民 $a$ 的家和村民 $b$ 的家之间存在一条路径。

输出格式

一行输出两个数字 $x$ 和 $y$。

$x$ 表示村长将会在哪个村民家中举办会议。

$y$ 表示距离之和的最小值。

输入输出样例 #1

输入 #1

输出 #1

2 4

说明/提示

数据范围

对于 $70%$ 数据 $n \le 10^3$。

对于 $100%$ 数据 $n \le 5 \times 10^4$。

思路分析 + 代码实现

树的重心

树的重心的有关证明在这里均省略

定义：

无根树 $T$ 中的结点 $v$ 是它的重心，当且仅当以下任意一条成立：

在树中删去结点 $v$ 后，得到的图 $T\setminus{v}$ 中每个连通分量的大小均不超过原树结点数的一半。

在所有删去某个结点后得到的最大连通分量大小中，删去结点 $v$ 时所得到的值最小。

树中所有结点到某个结点的距离和中，到结点 $v$ 的距离和最小。 引自OI Wiki

由定义 3 可知，本题需要求树的编号较小的重心（树的重心如果不唯一，则恰有两个）

求法：

根据重心的等价定义，有 DFS 统计子树大小 和 换根 DP 统计深度和 两种方法可以在 $O(n)$ 时间内求出树的所有重心。这里用第一种。

用 $sz[i]$ 储存以节点 $i$ 为根的子树大小（所有子树上节点数 + 该节点）。
用 $w[i]$ 储存节点 $i$ 的重量，即 $i$ 的所有子树大小（不包括该节点）的最大值。
对每个结点，记录它的所有子结点对应子树的大小，并更新 $w[i]$ 。再利用总结点数减去当前子树大小得到“向上”的子树的大小，再更新 $w[i]$ 。
如果 $w[i] \leq n / 2$ ，则节点 $i$ 符合重心的定义，更新重心。

本题代码如下（树的重心求法见函数 get_center ）

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 5e4 + 5;
int w[MAXN], dep[MAXN], sz[MAXN], n;
vector<int> G[MAXN];
void get_center(int u, int f, int &tar) {
    sz[u] = 1;
    for(int v : G[u]) {
        if (v == f) continue;
        get_center(v, u, tar);
        sz[u] += sz[v];
        w[u] = max(w[u], sz[v]);
    }
    w[u] = max(w[u], n - sz[u]);
    if (w[u] <= n / 2)
        tar = min(tar, u);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int u, v, i = 1; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int center = MAXN, ans = 0;
    get_center(1, 0, center);
    queue<int> Q;
    Q.push(center);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int v : G[u]) {
            if (dep[v] || v == center) continue;
            dep[v] = dep[u] + 1;
            ans += dep[v];
            Q.push(v);
        }
    }
    cout << center << ' ' << ans;
    return 0;
}

其中 BFS 求距离和（深度和）也可以用 DFS ，代码如下：

int dfs(int u, int f) {
    int acc = dep[u];
    for(int v : G[u]) {
        if (v == f) continue;
        dep[v] = dep[u] + 1;
        acc += dfs(v, u);
    }
    return acc;
}
int main() {
    // 省略读入和求重心
    int ans = dfs(center, 0);
    cout << center << ' ' << ans;
    return 0;
}