中心 / 偏心距
树的直径·核
本课摘要
中心 / 偏心距课程回答“偏心距与树中心如何由向下和向上信息共同得到”。内容以树的直径·核为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。
- 判断中心 / 偏心距的适用条件与状态边界
- 围绕“树的直径·核”推导转移与计算顺序
- 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节
正在整理目录…
给每个点算「到最远点有多远」
换根的第三类目标是偏心量：对每个点 ，求它的偏心距 = 「 到树上最远点的距离」。偏心距最小的点就是树的中心，最小值叫半径； 所有偏心距里的最大值 = 树的直径（最长链长度）。
又是「对每个点都要一个答案」的形状。朴素做法照旧 （每点各 BFS 求最远）。 换根 DP 把它压到 ：每个点的最远点，要么在它的子树里（向下），要么在子树外（经父亲向上）——两支取较大。
与 F 部分·直径/重心 DP 的分工
「树的直径」本身有一套固定根一遍 DFS 的经典求法（子树最深链 + 次深链拼出过点最长路径）， 那是 F 部分·直径 / 重心 DP 的主场，含完整推导。本页站在换根视角：不止求「一条直径」，而是给每个点都算出偏心距（二次扫描逐点求最远），两页互补——先在 F 学会「一条最长链」，再来这里学「每点的最远」。
两遍扫描：向下最长链 + 向上最长链
第一遍 · 后序，求「向下最长链」。对每个点 ，记它子树内向下的最长链 和次长链 （次长必须来自与最长不同的孩子）。为什么要次长？换根时可能要「避开某个孩子」，届时就得退而求其次。
第二遍 · 前序，求「向上最长链」。孩子 经父 往上能走多远？ 两条候选：走 自己的向上链 ，或走 的「避开 那支」的向下最长链—— 若 恰是贡献 的那个孩子，就只能用 ，否则用 。取较大再加这条边：
合成偏心距：
本质
「每点偏心距」就是「每点的最远」这个换根问题。第一遍备好向下最长/次长两条链， 第二遍把向上最长链沿边传下去；「避开自己那支」正是换根一贯的「父贡献减去本孩子子树」—— 只不过这里的聚合是取 而非求和。有了每点偏心距，中心 / 半径 / 直径一并落袋。
跟着算一遍
主链 加一个分支 （无权）。固定根 1，逐步：
看每点偏心距与中心
逐点统计是换根的通用形
回头看：距离和、距离分层点权和、偏心距——它们表面差别很大，但换根的骨架完全一样： 第一遍后序把「子树内的某个聚合」备好，第二遍前序用「父的信息减去本孩子那份，再沿边合并」把「子树外」补齐， 每点答案 = 内 + 外。变的只是聚合方式：求和（距离和 / 点权和）还是取 （偏心距）。
像「医院设置」（）这类，本质就是逐点距离和统计：换根一遍求出每个点作医院的总代价，再取最优。 换根让你把「对每个候选点各评估一次」的 收成 ——这正是换根 DP 最通用的用途。
易错点
求偏心距务必维护次长链 与「贡献最长链的孩子编号」：换根到那个孩子时必须避开它自己、改用次长，否则会把「自己走出去又走回来」的假链算进最远。 「避开自己那支」是所有 型换根的通病，格外小心。
例题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100005;
int n;
vector<int> g[N];
int down1[N], down2[N], best[N], up[N]; // 向下最长/次长链、贡献最长的孩子、向上最长链
int ecc[N]; // 偏心距 = max(down1, up)
// 第一遍：后序求每点向下最长/次长链
void dfs1(int u, int fa)
{
down1[u] = down2[u] = 0;
best[u] = -1;
for (int v : g[u])
{
if (v == fa) continue;
dfs1(v, u);
int cand = down1[v] + 1; // 经孩子 v 向下最长
if (cand > down1[u])
{
down2[u] = down1[u];
down1[u] = cand;
best[u] = v;
}
else if (cand > down2[u])
down2[u] = cand;
}
}
// 第二遍：前序求向上最长链 up[]，合成偏心距
void dfs2(int u, int fa)
{
for (int v : g[u])
{
if (v == fa) continue;
// v 往上：父的 up 或父『避开 v 这支』的最长向下链，取大 + 1
int uDown = (best[u] == v) ? down2[u] : down1[u];
up[v] = max(up[u], uDown) + 1;
dfs2(v, u);
}
}
int main()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs1(1, 0);
up[1] = 0;
dfs2(1, 0);
int center = 1;
for (int i = 1; i <= n; i++)
{
ecc[i] = max(down1[i], up[i]); // 每点到最远点的距离
if (ecc[i] < ecc[center]) center = i; // 偏心距最小 = 树的中心
}
cout << center << " " << ecc[center] << endl; // 中心及其偏心距（半径）
return 0;
}#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 105;
int n;
ll c[N];
vector<int> g[N];
ll sz[N], f[N], W;
void dfs1(int u, int fa, ll dep)
{
sz[u] = c[u];
f[1] += c[u] * dep;
for (int v : g[u]) if (v != fa) { dfs1(v, u, dep + 1); sz[u] += sz[v]; }
}
void dfs2(int u, int fa)
{
for (int v : g[u]) if (v != fa)
{
f[v] = f[u] + (W - 2 * sz[v]); // 逐点距离和：换根一次性求全
dfs2(v, u);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int l, r;
cin >> c[i] >> l >> r;
W += c[i];
if (l) { g[i].push_back(l); g[l].push_back(i); }
if (r) { g[i].push_back(r); g[r].push_back(i); }
}
dfs1(1, 0, 0);
dfs2(1, 0);
ll ans = f[1];
for (int i = 2; i <= n; i++) ans = min(ans, f[i]); // 逐点统计后取最优
cout << ans << endl;
return 0;
}