先以 1 为根求深度和与子树大小，再用换根公式线性求出每个根的深度和。
OJ: luogu
题目 ID: P3478
难度:普及+/提高
标签:树形结构换根DP动态规划
日期: 2026-06-22 23:11
题意
给定一棵 n 个点的树。任选一个点作为根后，每个点的深度等于它到根的边数。要求找一个根，使整棵树所有点的深度之和最大。
样例中输出 7 或 8 都可以，因为它们对应的深度和相同。
思路
最直接的办法是枚举每个点作为根，然后从这个点 BFS 一次，算出它到所有点的距离和。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：每个点都 BFS 计算距离和，只适合小数据。
const int MAXN = 505;
int n;
vector<int> graph_edges[MAXN];
long long distance_sum_from(int start) {
int dist[MAXN];
for (int i = 1; i <= n; i++) {
dist[i] = -1;
}
queue<int> que;
que.push(start);
dist[start] = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = 0; i < (int)graph_edges[u].size(); i++) {
int v = graph_edges[u][i];
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
que.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; i++) {
int u, v;
cin >> u >> v;
graph_edges[u].push_back(v);
graph_edges[v].push_back(u);
}
int best_node = 1;
long long best_value = distance_sum_from(1);
for (int i = 2; i <= n; i++) {
long long value = distance_sum_from(i);
if (value > best_value) {
best_value = value;
best_node = i;
}
}
cout << best_node << '\n';
return 0;
}这个做法一次 BFS 是 n=10^6 的数据。
考虑先把树临时扎根在 1。我们可以一次遍历得到每个点的深度，所以 dist_sum[1] 就是所有深度之和。同时再求出每个点的子树大小 subtree_size[u]。
关键是换根。假设当前根是 u，要把根换到 u 的儿子 v：
v子树内一共有subtree_size[v]个点，它们离新根都近了1；- 其余
n - subtree_size[v]个点，它们离新根都远了1。
所以有：
text
dist_sum[v] = dist_sum[u] - subtree_size[v] + (n - subtree_size[v])从 1 出发沿树边把这个公式推下去，就能在线性时间内求出每个点作为根的深度和。最后扫描一遍，取 dist_sum 最大的点即可。代码中使用队列生成遍历顺序，再逆序统计子树大小，避免 n=10^6 时递归爆栈。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n;
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt;
int parent_node[MAXN];
int subtree_size[MAXN];
int depth_node[MAXN];
long long dist_sum[MAXN]; // dist_sum[u] 表示以 u 为根时，所有点深度之和。
vector<int> order_nodes;
void add_edge(int u, int v) {
edge_cnt++;
to[edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void read_input() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
}
void build_order() {
order_nodes.reserve(n);
queue<int> que;
que.push(1);
parent_node[1] = 0;
depth_node[1] = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
order_nodes.push_back(u);
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
if (v == parent_node[u]) {
continue;
}
parent_node[v] = u;
depth_node[v] = depth_node[u] + 1;
que.push(v);
}
}
}
void solve() {
build_order();
long long root_sum = 0;
for (int i = 0; i < (int)order_nodes.size(); i++) {
int u = order_nodes[i];
subtree_size[u] = 1;
root_sum += depth_node[u];
}
dist_sum[1] = root_sum;
for (int i = (int)order_nodes.size() - 1; i >= 0; i--) {
int u = order_nodes[i];
if (parent_node[u] != 0) {
subtree_size[parent_node[u]] += subtree_size[u];
}
}
for (int i = 0; i < (int)order_nodes.size(); i++) {
int u = order_nodes[i];
for (int e = head[u]; e != 0; e = nxt[e]) {
int v = to[e];
if (v == parent_node[u]) {
continue;
}
// 根从 u 换到孩子 v：
// v 子树内的点深度都 -1，其余点深度都 +1。
dist_sum[v] = dist_sum[u] - subtree_size[v] + (n - subtree_size[v]);
}
}
int best_node = 1;
for (int i = 2; i <= n; i++) {
if (dist_sum[i] > dist_sum[best_node]) {
best_node = i;
}
}
cout << best_node << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
时间复杂度为
空间复杂度为
总结
这题的核心不是重新 DFS 每个根，而是观察换根时距离和的变化量。只要知道儿子子树大小，根从父亲换到儿子的答案就能
实现时要注意数据范围很大，深度和需要 long long，遍历最好写成非递归形式。