F树形 DP

直径 / 重心 DP

过点最长链

本课摘要

直径 / 重心 DP课程回答“过当前节点的多条链如何组合出直径与重心信息”。内容以过点最长链为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断直径 / 重心 DP的适用条件与状态边界
  • 围绕“过点最长链”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

树里最长的那条路，怎么一遍找出来

树的直径：任意两点间最长的那条路径。它是许多问题的地基——树网的核、时态同步、乃至距离统计，都要先抓住这条最长路。

最长路可能不经过根，也可能在树的任意角落拐弯。枚举所有点对求最短路再取最大？O(n2)O(n^2) 起步，n=105n=10^5 扛不住。 但换个视角就豁然开朗：任何一条路径，都必有一个「最高点」（深度最浅的那个点）。

于是只要枚举这个最高点 uu，问题就变成：以 u 为「屋脊」，向它的两个不同孩子方向各挂一条最长的向下链，拼起来就是「过 u 的最长路径」。全局直径 = 所有点的「过点最长」取最大。

u拐点 u最深链次深链每个点当一次「拐点」，取它两条最深的向下链拼起来——全局最大即直径。
过点 u 的最长路径 = u 的最深孩子链 + 次深孩子链；每个点只在自己当「屋脊」时贡献一次。

状态：向下最长链 down[u]

只需一个状态：down[u]down[u] = 从 u 出发、一路向下（进入子树）、必含 u 的最长链的长度。它由孩子递推：

down[u]=max⁡c∈son(u)(down[c]+wu,c)(;0)down[u]=\max_{c\in son(u)}\big(down[c]+w_{u,c}\big)\quad(\text{;}0)

取所有孩子里「孩子链 + 连边」最大的那一条。叶子没有孩子，down[leaf]=0down[\text{leaf}]=0。

而「过 u 的最长路径」要拿两条：在遍历孩子时顺手维护最大 best1best_1 与次大 best2best_2 两条向下链，则

through(u)=best1+best2,diam=max⁡uthrough(u)\text{through}(u)=best_1+best_2,\qquad \text{diam}=\max_u \text{through}(u)

两条链必须来自不同孩子（否则会走回头路），所以取「最大 + 次大」而非「最大 + 最大」。

1523344152金色序号 = 处理次序：叶子 4、5 先算好，父亲 2 才能合并；根 1 最后收口。
后序遍历：down[c]down[c] 先算好，父亲才能在合并孩子时同步更新 best1,best2best_1,best_2 与全局答案。

本质

直径不需要「两遍 BFS」也不需要换根——一遍后序 DFS 就够：每个点在合并孩子的那一瞬间，用「最深 + 次深」结算过它的最长路径。把「枚举最高点」这个观察落实成状态，O(n2)O(n^2) 塌成 O(n)O(n)。

跟着算一遍

小树（点权当作到父亲的边权简化演示）：根 11 带 2,32,3；22 带 4,54,5；33 带 66。设各点权 w=[2,3,4,5,1,6]w=[2,3,4,5,1,6]，把「过点链」当作点权和：

1
叶子 4、5、6。 down[4]=4, down[5]=1, down[6]=6down[4]=4,\ down[5]=1,\ down[6]=6（叶子的向下链就是自己的权）。
2
节点 2（权 3，孩子 4、5）。孩子链 4,14,1，最大 4、次大 1。down[2]=3+4=7down[2]=3+4=7；过 2 的链 =3+4+1=8=3+4+1=8。
3
节点 3（权 1，孩子 6）：down[3]=1+6=7down[3]=1+6=7，过 3 只有一条孩子链，through=1+6=7through=1+6=7。 根 1（权 2，孩子 2、3）：孩子链 down[2]=7,down[3]=7down[2]=7,down[3]=7，through(1)=2+7+7=16through(1)=2+7+7=16。
✓
直径 max⁡(8,7,16,… )=16\max(8,7,16,\dots)=16——峰顶在根 1，链是「4→2→1→3→6」。
下面的演示逐点点亮 down[u]down[u]，末帧把「拐点 + 两条最深链」高亮成绿色；改点权看直径与峰顶如何移动。

看直径在哪拐弯

改点权，看每个点的向下最长链 down 与「过点」最长链
1
点 1 · 点权
2
2
点 2 · 点权
3
3
点 3 · 点权
4
4
点 4 · 点权
5
5
点 5 · 点权
1
6
点 6 · 点权
6
节点下方 ↓down = 从该点向下、必含它的最长链权和。过某点的最长链 = 它两条最深孩子链拼起来 + 自身权。 全局最长（带权直径）= 20，峰顶在 1 号。
1w=22w=33w=44↓55w=16w=6
已暂停，第 1 步，共 6 步，1 倍速
当前处理 直径峰顶 + 链
叶子 4：down=5，过点链=5。

同一套合并：最大子树和

把「链」换成「块」，同一套自底向上合并就解另一类题：树上点权有正有负，求一个连通块使权和最大。 状态 f[u]f[u] = 含 u 的最大子树权和：

f[u]=wu+∑c∈son(u)max⁡(0, f[c])f[u]=w_u+\sum_{c\in son(u)}\max\big(0,\ f[c]\big)

盯住那个 max⁡(0,f[c])\max(0,f[c])：孩子这块若净收益为正就接上，为负就剪断（宁可不要）。答案 = max⁡uf[u]\max_u f[u]。 这和直径的「孩子链为正才接」是同一个直觉——只不过直径挑「最深两条」，子树和是「所有正的都要」。

常见陷阱：负权不能一律截断到 0

f[u]f[u] 起手要塞 wuw_u（即使它是负数），只有孩子的块才用 max⁡(0,⋅)\max(0,\cdot) 决定接不接。若把 f[u]f[u] 也钳到非负，全负的树会错报 0。答案初值也要设成 −∞-\infty 而非 0，防止「必须选至少一个点」时被 0 顶掉。

换个视角看直径。本页从「固定根、一遍 DFS」求出直径与过点最长链；若要对每个点都问「以它为端点的最远距离（偏心距）」，则需要换根 DP 把父方向的信息也回推——那条路线见 E 部分 · 中心 / 偏心距。两条路互补：这里主讲直径本身的推导，换根篇主讲逐点偏心距。

顺带说重心。树的重心是这样一个点：以它为根时，最大的那棵子树节点数最小。 一遍 DFS 求出每点的子树大小 sz[u]sz[u]，判据是——u 的各个方向（每个孩子子树，以及「上方」n−sz[u]n-sz[u]）都 ≤n/2\le n/2 时，u 即重心。它和直径同属「一遍 DFS 抓全局结构」的固定根树形 DP。

重心重心：以它为根时，最大子树的节点数最小；各方向最均衡。
重心：删去它后剩下的最大连通块最小——各方向最均衡。用子树大小 sz[u]sz[u] 一遍判定。

例题

P1099[NOIP2007] 树网的核NOIP 2007 提高组提高+/省选-
题意
带权树上找一条长度 ≤s\le s 的路径（「核」），使全树到这条路径的最大距离（偏心距）最小。
对应关系
先求直径（本类核心）：最优核一定落在某条直径上。沿直径滑动长度 ≤s\le s 的窗口，配合每点「向直径外伸出的最长链」，取偏心距最小。
为什么选它
直径 + 核 + 最小偏心距三件套集大成的 NOIP 真题。一次把「一遍 DFS 求直径」用到实处，是本类当之无愧的主讲位。
转移 · 复杂度
down[u]=max⁡(down[c]+w)down[u]=\max(down[c]+w) 求直径；再沿直径双指针，O(n)O(n)。
参考代码（一遍 DFS 求直径，核部分见题解）
C++
在洛谷打开 P1099 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100005;
struct E { int to, w; };
vector<E> g[N];
long long down[N];            // down[u]：从 u 向下、必含 u 的最长链长
long long ans;               // 全局直径

void dfs(int u, int fa)
{
    down[u] = 0;
    long long best1 = 0, best2 = 0;      // 两条最长的孩子向上链
    for (E e : g[u])
    {
        if (e.to == fa) continue;
        dfs(e.to, u);
        long long chain = down[e.to] + e.w;   // 孩子链 + 连它的边
        if (chain > best1) { best2 = best1; best1 = chain; }
        else if (chain > best2) best2 = chain;
    }
    down[u] = best1;                     // 向下最长 = 最深的一条
    ans = max(ans, best1 + best2);       // ★过 u 的最长 = 两条最深拼接
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    dfs(1, 0);
    cout << ans << endl;                 // 一遍 DFS 即得直径
    return 0;
}
P1122最大子树和洛谷原生普及/提高-
题意
树上每点有一个「美丽值」（可负）。删去若干点后要剩下一个连通块，求块内美丽值之和的最大值。
为什么选它
f[u]f[u] = 含 u 的最大子树和，链式合并、无背包维度，是「过点最优」最轻量的载体。与直径共享「孩子为正才接」的剪枝直觉，正好巩固。
转移 · 复杂度
f[u]=wu+∑max⁡(0,f[c])f[u]=w_u+\sum\max(0,f[c])，答案 max⁡uf[u]\max_u f[u]；O(n)O(n)。
参考代码
C++
在洛谷打开 P1122 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 16005;
vector<int> g[N];
int w[N];                     // 点权（可正可负）
int f[N];                     // f[u]：含 u 的最大子树权和
int ans;

void dfs(int u, int fa)
{
    f[u] = w[u];              // 至少含它自己
    for (int v : g[u])
    {
        if (v == fa) continue;
        dfs(v, u);
        if (f[v] > 0) f[u] += f[v];      // ★孩子块为正才接上，否则截断
    }
    ans = max(ans, f[u]);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    ans = -0x3f3f3f3f;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

练习

P1131[ZJOI2007] 时态同步让所有叶子到根的路径等长，只能增加边权。f[u] = u 子树内最长链；每条子边补齐到最长，累计增量。是「直径式合并」的变体。在洛谷打开
P1364医院设置带点权的重心：找一个点使 Σ(点权 × 到它的距离) 最小。n≤100 可先暴力，再用子树大小判重心对照，纯重心练习。在洛谷打开
P1122最大子树和（自测）独立写一遍：注意 f[u] 起手含 w[u]（可负），孩子块 max(0, f[c]) 才接，答案初值 -∞。在洛谷打开

已进入 直径 / 重心 DP · 树形 DP · DP大师