用子树大小和换根 DP 求树上距离和最小的节点。
OJ: luogu
题目 ID: P1395
难度:普及+/提高-
标签:树形 DP换根 DPpython
日期: 2026-07-17 02:00
题意
选择会议点，使所有节点到它的距离和最小；相同距离时取编号小的点。
思路
以 1 为根求 subtree[u] 和 sum[1]。根从 u 移到儿子 v 时，v 子树内的点距离减 1，其余点距离加 1，所以 sum[v] = sum[u] + n - 2*subtree[v]。
Python 知识
reversed(order[1:])完成自底向上子树统计。min(range(...), key=lambda node: (...))同时处理最小值和编号 tie-break。- 非递归遍历不会在链形树上触发调用栈限制。
代码
python
import sys
input = sys.stdin.buffer.readline
n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
parent = [0] * (n + 1)
depth = [0] * (n + 1)
order = [1]
for node in order:
for neighbor in graph[node]:
if neighbor != parent[node]:
parent[neighbor] = node
depth[neighbor] = depth[node] + 1
order.append(neighbor)
subtree_size = [1] * (n + 1)
for node in reversed(order[1:]):
subtree_size[parent[node]] += subtree_size[node]
distance_sum = [0] * (n + 1)
distance_sum[1] = sum(depth)
for node in order[1:]:
distance_sum[node] = distance_sum[parent[node]] + n - 2 * subtree_size[node]
answer = min(range(1, n + 1), key=lambda node: (distance_sum[node], node))
print(answer, distance_sum[answer])原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
int n;
vector<int> g[MAXN];
int parent_node[MAXN];
int order_arr[MAXN], order_cnt;
int subtree_size[MAXN]; // subtree_size[u] 表示以 1 为根时 u 子树的大小
long long dist_sum[MAXN]; // dist_sum[u] 表示所有点到 u 的距离和
void compute_depth_sum_and_size() {
queue<int> q;
static int depth[MAXN];
q.push(1);
parent_node[1] = 0;
depth[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[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[v] = depth[u] + 1;
q.push(v);
}
}
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];
}
}
}
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;
// 根从 u 移到儿子 v：
// v 子树里的点距离都 -1，其余点距离都 +1。
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);
}
compute_depth_sum_and_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;
}复杂度
时间 O(n)，空间 O(n)。
总结
换根公式把每条边两侧的规模差直接变成距离和变化量。