树形DP教程：从递归视角彻底搞懂树上DP

ZhangChuan1350 · 2026-02-16 18:12:55 · 算法·理论

前言

在开始树形 DP 之前，你只需具备这三点要求：

了解树的各项概念和定义。
会用邻接表存一棵树。
会写 DFS 遍历树（知道怎么避免走回父节点）。

本文代码均使用 vector 存图，如果你习惯链式前向星，附录里有转换说明。
两种方式本质一样，选你顺手的就行。

由于树形 DP 题目变化多端，本文采用一点一例的方式——一个核心思想，配一道经典题。

注：在本文中，符号“\gets”表示赋值。

附录 A 中有树的基本定理证明。在正文中，通过中括号数字的上标形式来体现其位置。
例如：“^{[x]}” 表示在附录 A 的第 x 个位置。

基础树形 DP

例题说明：采用洛谷 P1352 没有上司的舞会、洛谷 P2016 战略游戏和洛谷 P1122 最大子树和作为经典例题讲解。

本文默认你已经了解题意。

洛谷 P1352 没有上司的舞会

题目可以抽象为：
有一棵树，共有节点 n 个，编号为 i\in[1,n]，快乐指数为 r_i，要求选择若干个节点，使得：

任意一对父节点和子节点最多选一个。
最大化快乐指数。

思路： 可以发现，每个结点有且只有 2 种情况——选或不选，只需记录此状态即可。因为树形结构决定了通过递归必须从根向下传递信息，所以一般题目给出或自己选择选一个根，因此：

定义状态 f_{u,0/1}，表示以编号为 u 的节点为根节点，是否选择节点 u 的最大快乐指数。

则我们可以轻易得到**状态初始化**： - $f_{u,0}\gets0$，不选节点 $u$，初始快乐指数为 $0$。 - $f_{u,1}\gets r_u$，选择节点 $u$ ，加上结点 $u$ 的快乐指数 $r_u$。 **状态转移方程**可以这样想：假设 $\operatorname{son}(u)$ 表示 $u$ 的所有子节点的集合（后文不再说明），那么： - 不选节点 $u$，则每个子节点 $v$ 可以选择取或不取，我们取每个子节点的最优值，并求和。即 $$f_{u,0}\gets f_{u,0}+\sum_{v\in\operatorname{son}(u)}\max(f_{v,0},~f_{v,1})$$ - 选择节点 $u$，则所有子节点必须不选，因此 $$f_{u,1}\gets f_{u,1}+\sum_{v\in\operatorname{son}(u)}f_{v,0}$$ **注意**：在这题中，数据给出的是**有向边**，因此需找到**没有父节点**的结点——**根节点**（$\mathrm{root}$），以保证这棵树所有节点都被遍历完成。因为根节点也可能不选，所以答案不是简单的 $f_{\mathrm{root},1}$，而是两者取大，因此答案为 $$\max(f_{\mathrm{root},0},~f_{\mathrm{root},1})$$ 把状态转移**翻译**成代码，就是： ```cpp #include <bits/stdc++.h> using namespace std; constexpr int N=6e3+5; int n,r[N],f[N][2]; int root,father[N]; //记录 u 的父节点，用于寻找根 root vector<int>tree[N]; //存储 u 的所有子节点 void dfs(int u){ f[u][1]=r[u]; f[u][0]=0; for (const int &v:tree[u]){ dfs(v); f[u][1]+=f[v][0]; f[u][0]+=max(f[v][0],f[v][1]); } } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&r[i]); for (int i=1;i<n;++i){ int l,k; scanf("%d%d",&l,&k); tree[k].push_back(l); father[l]=k; //记录 l 的上司 k } for (int i=1;i<=n;++i) if (father[i]==0) root=i; //检查没有上司的结点 dfs(root); printf("%d",max(f[root][0],f[root][1])); return 0; } ``` > **❓ 为什么不需要记忆化？** > 你可能会问：**这个递归不会重复计算吗？需不需要加 `memo` 数组？** > **答案是：完全不需要。** > 看这段代码： > ```cpp > for (const int &v:tree[u]) { > dfs(v); > } > ``` > **每个子节点 $v$ 只会被它的父节点 $u$ 访问一次。** 因为树的结构决定了：**每个非根节点有且只有一个父节点**。 > > 换句话说： > - **在区间 DP 里**，同一个 $[l,r]$ 可能被**多个**大区间需要 $\to$ 需要记忆化。 > - **在树形 DP 里**，同一个节点 $v$ 只会被它的**唯一**父节点需要 $\to$ 天然避免重复计算。 > > 所以，你不需要 `memo`，不需要记忆化，**直接递归就能跑得飞快**。 > > 这不是**不用优化**，这是树这种结构**天生给你的福利**。 ## [洛谷 P2016 战略游戏](https://www.luogu.com.cn/problem/P2016) :::epigraph[**例题对比**] 这道题与 [P1352]((https://www.luogu.com.cn/problem/P1352)) 恰好对称——[P1352]((https://www.luogu.com.cn/problem/P1352)) 是**相邻节点不能都选**，这里是**相邻节点至少选一个**。这种对称性能帮你更深刻地理解状态设计。 ::: **题目可以抽象为：** 在一棵**无根树**上有 $n$ 个节点，其编号为 $i\in[0,~n-1]$，每个节点与其他 $k$ 个节点有一条**无向边**相连。当士兵站在节点 $u$ 时，所有与 $u$ 相连的**边**都可被瞭望到。要求放置若干个士兵，使得： - 所有边均被瞭望到。 - 放置的士兵数目最小。 --- **思路：** 可以发现，当这棵树的其中一条边被瞭望到时，必然有士兵在**父节点放置**或**子节点放置**，那么可认为是**相邻节点至少选 $1$ 个**。同理，每个结点有且只有 $2$ 中情况——**选**或**不选**，且我们通常从根节点开始考虑。因此：定义状态 $f_{u,0/1}$，表示以编号 $u$ 为根节点，是否在节点 $u$ 放置士兵的**最少士兵数目**。 $0$ 表示不放置，$1$ 表示放置。则初始化是显然的： - 当不在节点 $u$ 放置时，$f_{u,0}\gets0$。 - 当在节点 $u$ 放置时，$f_{u,1}\gets1$。 **状态转移方程**可以这样想： - 不在节点 $u$ 放置，则 $u$ 的子节点必须放置，在初始基础上加上子节点的值，也就是 $$f_{u,0}\gets f_{u,0}+\sum_{v\in\operatorname{son}(u)}f_{v,1}$$ - 在节点 $u$ 放置，则 $u$ 的子节点可放可不放，在初始基础上加上**放**与**不放**的**较小者**，也就是 $$f_{u,1}\gets f_{u,1}+\sum_{v\in\operatorname{son}(u)}\min(f_{v,0},~f_{v,1})$$ **注意**：本题中给的数据是**无向边**，构成的是**有根树**，把无根树转换为有根树的 DFS 方法在 **附录 A** 中提到，在此不详细说明。同理，根节点也可能不选，因此答案取**较小者**，为 $$\min(f_{\mathrm{root},0},~f_{\mathrm{root},1})$$ 把状态转移**翻译**成代码，就是： ```cpp #include <bits/stdc++.h> using namespace std; constexpr int root=0; //我们任意选择一个节点作为根，因为该题中，根的选择不影响最终结果 int n,r; int f[1505][2]; vector<int>g[1505],tree[1505]; //g 是原无根树，tree 是转换后的有根树 void dfs(int u,int dad){ //把无根树变为有根树 for (const int &v:g[u]){ if (v==dad) continue; tree[u].push_back(v); dfs(v,u); } } void dp(int u){ f[u][0]=0; f[u][1]=1; for (const int &v:tree[u]){ dp(v); f[u][1]+=min(f[v][0],f[v][1]); f[u][0]+=f[v][1]; } } int main() { scanf("%d",&n); while (n--){ int i,k; scanf("%d%d",&i,&k); while (k--){ scanf("%d",&r); g[i].push_back(r); g[r].push_back(i); } } dfs(root,-1); dp(root); printf("%d",min(f[root][0],f[root][1])); return 0; } ``` ## [洛谷 P1122 最大子树和](https://www.luogu.com.cn/problem/P1122) :::epigraph[**例题对比**] 这是一种**新的题目**，包含**负数处理**、**贪心思想**等方法。 ::: **题目可以抽象为：** 在一棵**无根树**上有 $n$ 个节点，其编号为 $i\in[1,n]$ ，那么有 $(n-1)$ 条边，每个节点有一个**节点权值 $b_i$（可能为负）**。要求去掉若干条边。去掉一条边时，必然生成两棵树，要求选择一棵树继续操作，最终使得： :::align{center} **在树中找一个连通子图，使得节点权值之和最大。** ::: --- **思路：** 可以发现，这道题目其实要求的是**连通块**中的节点的值，因此：定义 $f_u$ 表示以 $u$ 为根的子树中，包含 $u$ 的连通块的节点最大和。那么显然可以有初始化 $f_u\gets b_u$，因为子树肯定首先包含的就是**根节点**，其余子树暂时未算。 **状态转移方程**可以这样想：如果我们对这棵树的其中一条边作决策，有**剪**和**不剪**这两种方案？怎么选择呢？通过直觉，容易发现一个浅显道理： - 如果这条边连接的子树的节点权值和为**负数**，则不能保留，因为加上也会拖后腿。 - 如果节点权值和为**非负数**，一可以加上，这样可以**增加节点权值**。于是： $$f_u=b_u+\sum_{v\in\operatorname{son}(u)}\max(0,f_v)$$ > **理由：** 加上一个正数只会让和更大，加上一个负数只会让和更小，这是显然的。 **注意**： - 同样地，本题给定的数据为**无向边**，需要选择一个节点建树，本文的代码选择 $1$。 - 在本题中，我们定义的 $f_u$ 表示：以 $u$ 为根的子树中，必须包含 $u$ 的连通块的最大和。这个定义保证了我们算出的值只考虑那些**以 $u$ 为最高点**的连通块。但题目要的是整棵树中任意一个连通子树的最大和，这个连通块可能藏在树里的任何地方，因此需要考虑每个节点当根节点的情况。因此，最终答案为 $$\max(f_1,~f_2,~\dots,~f_n)$$ 把状态**翻译**成代码，就是： ```cpp #include <bits/stdc++.h> using namespace std; int n,b[16005],f[16005]; int ans=-2e9; vector<int>g[16005],tree[16005]; void build(int u,int fa){ for (const int &v:g[u]){ if (v==fa) continue; tree[u].push_back(v); build(v,u); } } void dp(int u){ for (const int &v:tree[u]){ dp(v); //是正就加，非正不加 if (f[v]>0) f[u]+=f[v]; } } int main() { scanf("%d",&n); for (int i=1;i<=n;++i){ scanf("%d",&b[i]); f[i]=b[i]; } for (int i=1;i<n;++i){ int a,b; scanf("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } build(1,0); dp(1); for (int i=1;i<=n;++i) ans=max(ans,f[i]); printf("%d",ans); return 0; } ``` # 树形背包 **例题说明**：采用 [洛谷 P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015) 和 [洛谷 P2014 选课](https://www.luogu.com.cn/problem/P2014)作为经典例题讲解。 **承接**：在《[进阶背包DP教程：基础背包的综合运用](https://www.luogu.com.cn/article/u1b3q8nf)》中留下的**常见问题解答**中，留下了**依赖背包**的悬念：**依赖背包**和**树形背包**到底是什么关系？本文将理清树形背包，你会发现，依赖背包——不过是它的一种特例。本文默认你已经了解题意。 ## [洛谷 P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015) **题目可以抽象为：** 有一棵树（**二叉树**在推导中无义），共有结点 $N$ 个，编号为 $i\in[1,N]$；有边 $(N-1)$ 条，编号为 $j\in[1,N-1]$，其边权为 $w_j$，要求保留 $Q$ 条边，使得： - 保留的这 $Q$ 条边构成一棵连通树。 - 最大化总边权之和。可以看出，这其实是一个背包问题：选若干条边，同时最大化总边权。只不过这是在**树**上的背包，因此被称为**树形背包**。 --- **思路：** 可以发现，如果**去掉**一条边，则必然会将这棵树分割为两棵不连通的树 $^{[1]}$。因此，如果我们想在一棵子树中**保留**一条边，则**必须先选它和父节点之间的那条边**，否则那个儿子所在的子树根本进不来。 > **形象化描述**：父节点到子节点的边，就是子节点所在子树的**入场券**。你想进一个房间（子树），必须先买一张门票（选父边）。定义参数 $w_{u,v}$ 表示该树的无向边 $(u,v)$ 的权值。也就是说，$w_{u,v}$ 等价于 $w_{v,u}$。则定义状态 $f_{u,j}$ 表示在以 $u$ 为根的子树中，选 $j$ 条边，**且 $u$ 必须与父节点相连**的最大边权。 **状态转移方程**可以这样想：对于 $\forall~v\in\operatorname{son}(u)$，如果我们决定保留 $(u,v)$ 这条**入场边**（花费 $1$ 条边的容量），并分配给 $v$ 的子树 $k$ 条边，那么总贡献为 $$ f_{u,j}\gets\max_{k\in[0,j)}\begin{cases} f_{u,j}\\ f_{u,j-k-1}+f_{v,k}+w_{u,v} \end{cases} $$ > 这里的 $k<j$ 是为了保证还有容量放进这个**入场券**。当我们用代码实现这个转移时，**要注意**：$f_{u,j}$ 的更新依赖于**还没有考虑当前子节点 $v$ 时的 $f_{u,*}$ 值**，这与《[背包DP教程：从DFS暴力到DP的逐步推导](https://www.luogu.com.cn/article/s3dkf9lf)》中 **01 背包降维优化**的要求一致，因此 $j$ 需**倒序遍历**，以保证每个子节点有且只有被使用 $1$ 次。完整代码如下： ```cpp #include <bits/stdc++.h> using namespace std; struct Edge{ int to,w; }; vector<Edge>g[105],tree[105]; int n,q,f[105][105]; void build(int u, int fa){ for (const auto &e:g[u]){ int v=e.to,w=e.w; if (v==fa) continue; tree[u].push_back({v,w}); build(v,u); } } void dp(int u) { for (const auto &e:tree[u]){ int v=e.to,w=e.w; dp(v); for (int j=q;j>=0;--j){ //倒序遍历以保证只选 1 次 for (int k=0;k<j;++k){ f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+w); } } } } int main() { scanf("%d%d",&n,&q); for (int i=1;i<n;++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } build(1,0); dp(1); printf("%d",f[1][q]); return 0; } ``` ## [洛谷 P2014 选课](https://www.luogu.com.cn/problem/P2014) **题目可以抽象为：** 有若干个有向图，它们总共有 $N$ 个节点和 $N$ 条边，节点编号为 $i\in[1,N]$，每个节点有一个**节点权值** $s_i$，每个节点最多有 $1$ 个前驱。若要选择一个节点，则必须选择其前驱的节点。现要求： - 选择 $M$ 个节点。 - 最大化**节点权值**。 > 可以看出，这是一个**加强版**依赖背包，有了多层依赖。 > 同时，物品件数为 $N$，背包容量为 $M$，第 $i$ 件物品价值为 $s_i$、重量为 $1$。 --- **思路：** 注意到 `题目保证课程安排无冲突` 这句话，表明题目给出的数据**没有环**，也就是说，题目给出的若干个有向图其实都是**有层级的树**。既然题目给出的有向图是**若干个**，为了方便统计，我们可以引入一个**虚根 $0$**，它不占用背包容量，同时它的节点权值为 $0$。虚根 $0$ 与各个树的根节点相连，并且箭头指向各子树的真根节点。不难发现，此时节点数为 $(N+1)$，边数为 $N$，根据图论基本定理 $^{[2]}$，这样的图是一个**有层级的树**。则定义状态 $f_{u,j}$ 表示在以 $u$ 为根的子树中，选 $j$ 门课，**且 $u$ 必须选**。则初始化是显然的：$f_{u,1}=s_u$，因为若选 $1$ 门课，则必须选择根节点 $u$。 **没有入场券**的状态转移方程： $$ f_{u,j}\gets\max_{k\in[0,j]}\begin{cases} f_{u,j}\\ f_{u,j-k}+f_{v,k} \end{cases} $$ 最终答案：$f_{0,M+1}$，由于有虚根 $0$，因此背包容量是 $(M+1)$。 **注意：** - 虽然虚根 $0$ 不占用背包容量，但是必须选择它，否则其余节点无法选择。因此背包容量需增加 $1$，实际代码中的背包容量为 $(M+1)$。 - 这里没有**入场券**，因此 $k$ 的取值范围为 $k\in[0,j]$，同时那个 $-1$ 也会消失。 - 同理，由于每件物品最多选 $1$ 次，因此 $j$ 同样需要**倒序枚举**。 - 在编码中，输入 `m` 后需再加 $1$，以兼容背包容量，转移时直接使用加 $1$ 后的 `m` 即可。 **最重要的几点：** - 数组 $f$ 需初始化为 $-\infty$，因为需要表明这是**非法状态**。我在《[背包DP教程：从DFS暴力到DP的逐步推导](https://www.luogu.com.cn/article/s3dkf9lf)》中的**常见问题解答**中明确指出：若要求**恰好装满**，则应初始化为 $-\infty$。本题中 **`选择 M 门课程学习`** 说明了本题需要**恰好装满**。同时，若用 $-1$ 表示**非法状态**，需要判断 $f_{u,j-k}\ne-1\text{ 且 }f_{v,k}\ne-1$ 才能成功转移，因为若 $f_{u,j-k}$ 和 $f_{v,k}$ 之中有任意一个是 $-1$，另外一个是**正数**，则该状态一定是非法的，但 $f_{u,j}$ 却变成了正数——**变成了合法的**！ $-\infty$ 的好处是：不管多少个正数与它相加，它都是负数——**非法状态**。 - 初始化没有 $f_{u,0}=0$，因为状态 $f_{u,j}$ 的定义最重要的是**必须选择根节点 $u$**，$f_{u,0}$ 既然是在这个子树不选，那怎么选择根节点 $u$ 呢？**因此 $f_{u,0}$ 是非法状态**，应设置为 $-\infty$。参考代码如下： ```cpp #include <bits/stdc++.h> using namespace std; int n,m,f[305][305],s[305]; vector<int>g[305]; void dp(int u){ f[u][1]=s[u]; for (const int &v:g[u]){ dp(v); for (int j=m;j>=0;--j){ for (int k=0;k<=j;++k){ f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]); } } } } int main() { memset(f,0xcf,sizeof f); scanf("%d%d",&n,&m); ++m; for (int i=1;i<=n;++i){ int k; scanf("%d%d",&k,&s[i]); g[k].push_back(i); } dp(0); //从虚根 0 开始 printf("%d",f[0][m]); return 0; } ``` # 换根 DP **例题说明**：采用 [洛谷 P3478 STA-Station](https://www.luogu.com.cn/problem/P3478) 和 [洛谷 P2986 Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986)。本文默认你已经了解题意。 ## [洛谷 P3478 STA-Station](https://www.luogu.com.cn/problem/P3478) **题目可以抽象为：** 一棵**无根树**上有 $n$ 个节点，存在 $(n-1)$ 条无向边。定义**深度**：一个结点的深度为该节点到根的简单路径上**边**的数量，因此**根节点的深度为 $0$**。需找出一个节点，使得： :::align{center} **以这个结点为根时，所有结点的深度之和最大。** ::: **注意：答案可能不唯一，题目要求仅输出 $1$ 个即可。** --- **思路：** 在一棵无根树上，如果变换根节点会怎么样？（后文以节点 $1$ 为根的树称为**原树**） :::align{center} ![根据样例数据生成的树](https://cdn.luogu.com.cn/upload/image_hosting/dw2du7m2.png) ::: 先指定 $1$ 为根节点（指定哪个都行），则其他节点的深度呢？比如： - **节点 $1$**：深度为 $0$。 - **节点 $4$**：深度为 $1$。 - **节点 $2$**：深度为 $2$。现在**换根**！把根节点交给 $1$ 的子节点 $4$（后续称**新根**），那么，在**原图**中以节点 $4$ 为根的子树中，可以发现：其子树中的节点的**新深度**减少了 $1$。但是，不在原子树的节点，比如节点 $1$，很明显**新深度**增加了 $1$。以下是各个节点发生的变化： - 原图中在新根的子树**外**的节点： - **节点 $1$**：新深度为 $0+1=1$。 - 原图中在新根的子树**内**的节点： - **节点 $4$**：新深度为 $1-1=0$。 - **节点 $2$**：新深度为 $2-1=1$。 **总结**：当**原根**将根节点换到其子节点作为**新根**时，**原子树**中，以**新根**为根的子树中的所有节点均与**根节点**减小了 $1$ 的距离，子树外的所有节点均与**根节点**增加了 $1$ 的距离。定义参数 $\mathrm{size}_u$，表示在以 $1$ 为根节点的情况下，以 $u$ 为根的子树**所包含的节点总数**。对于 $\mathrm{size}_u$，其初始化为 $\mathrm{size}_u\gets1$，因为根节点也算 $1$ 个节点。 $\mathrm{size}_u$ 的**状态转移方程**：以 $u$ 为根的子树所包含节点，一定包含其子节点 $v$ 为根的子树所包含的节点子树，因此 $$\forall~v\in\operatorname{son}(u),~\mathrm{size}_u\gets\mathrm{size}_u+\mathrm{size}_v$$ --- 定义状态 $f_u$，表示当以 $u$ 为整棵树的根节点时，该树的深度。同时定义 $\mathrm{deep}_u$，表示节点 $u$ 的深度。因此 $\forall~v\in\operatorname{son}(u),~\mathrm{deep}_v=\mathrm{deep}_u+1$。则首先把 $1$ 当作根节点，以此来向子节点转移。则其初始化为 $f_1\gets f_1+\mathrm{deep}_u$。因此，对于 $u$ 子节点 $v$，对于以 $v$ 为根的子树的深度之和，分两类相加： - **子树内**：$f_u-\mathrm{size}_v$。以 $u$ 为根时，子树 $v$ 中所有节点的深度，比以 $v$ 为根时多 $1$，因此从 $f_u$ 换到 $f_v$ 时，需要先减去 $\mathrm{size}_v$。 - **子树外**：$n-\mathrm{size}_v$，共有 $n$ 个节点，因此 $v$ 子树外的节点共有 $(n-\mathrm{size}_v)$ 个。 - 因此，其相加之和为 $f_u-\mathrm{size}_v+n-\mathrm{size}_v=f_u+n-2\cdot \mathrm{size}_v

综上，状态转移方程为

\forall~v\in\operatorname{son}(u),~f_v\gets f_u+n-2\cdot\mathrm{size}_v

注意 n 的数据范围：1\leqslant n\leqslant10^6。int 会溢出，部分变量需要 long long。

根据状态转移方程直接翻译得出：

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e6+5;
vector<int>g[N];
int n,sz[N],root=1;
long long f[N],ans;
void build(int u,int fa,int deep){
    sz[u]=1; f[1]+=deep; //初始化
    for (const int &v:g[u]) {
        if (v==fa) continue;
        build(v,u,deep+1);
        sz[u]+=sz[v];
    }
}
void dfs(int u,int fa){ //换根
    for (const int &v:g[u]){
        if (v==fa) continue;
        f[v]=f[u]+n-2*sz[v];
        dfs(v,u);
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build(1,0,0); //根节点的深度为 0
    dfs(1,0);
    for (int i=1;i<=n;++i){
        if (f[i]>ans){
            ans=f[i];
            root=i;
        }
    }
    printf("%d",root); 
    return 0;
}

时间复杂度：两个 O(n) 的 DFS，加上最后处理结果 O(n)，总时间复杂度为 O(n)。

洛谷 P2986 Great Cow Gathering G

:::epigraph[例题对比] 和 P3478 相比，这里的深度换成了距离，节点数换成了奶牛数——但核心思想完全一样。

我们将复用 P3478 的子树内外思想，推导出带权的换根公式。 ::: 题目可以抽象为：
有一棵 N 个节点的无根树，节点编号为 i\in[1,N]，节点 i 有 c_i 头奶牛。
树有 (N-1) 条无向边，记 w_{u,v} 为边 (u,v) 的边权。

定义状态 f_X，表示以 X 为集会地点的不方便程度为

f_X=\sum_{i=1}^Nc_i\cdot\operatorname{dist}(i,X)

其中 \operatorname{dist}(i,X) 是节点 i 到 X 的树上唯一路径的距离（边权和）。

要求：找出一个节点 X，使得 f_X 最小。

特别地，当所有 c_i=1 且边权为 1 时，f_X 退化为 P3478 中的深度和。

在换根 DP 的视角下，我们把集会地点 X 视作整棵树的临时根——所有奶牛到它的距离，就是它们在以 X 为根的树中的带权深度。

思路： 回想 P3478 的 \mathrm{size}_u，原来表示节点总数，但在本题中，实际表示这棵树以 1 为总根时，以节点 u 为根的子树的奶牛数量，只不过 P3478 的每个节点的“奶牛数量”是 1 而已。

定义：

定义参数 \mathrm{cnt}，表示整棵树的奶牛数量，也就是
\mathrm{cnt}=\sum_{i=1}^Nc_i
这里的 \mathrm{cnt} 和 P3478 中的 “n” 功能相同。
定义参数 \mathrm{size}_u，在以 1 为总根的情况下，以 u 为根的子树的奶牛数量。
同理，其初始化为 \mathrm{size}_u\gets c_u，因为 u 是子树的根节点。
其转移方程同样是
\forall~v\in\operatorname{son}(u),~\mathrm{size}_u\gets\mathrm{size}_u+\mathrm{size}_v
根节点从 1 开始。由题目抽象部分容易得到 f_1 的初始化为
f_1=\sum_{i=1}^Nc_i\cdot\operatorname{dist}(i,1)

先来看看样例给的数据，这是通过样例生成的一棵树，节点上的数字代表其编号： :::align{center} ::: 发现：当根节点从 1 换到其子节点 3 时，原树中以 3 为根的子树中的所有节点均与 3 的距离减少了 w_{1,3}，同时其子树中的奶牛数量 \mathrm{size}_3，因此不方便程度减少了 \mathrm{size}_3\cdot w_{1,3}。
同时，原树中不在以 3 为根的子树中的节点增加了距离 w_{1,3}，且奶牛数量为总奶牛数量 \mathrm{cnt} 减去子树内的奶牛数量 \mathrm{size}_3，即不方便程度增加了 (\mathrm{cnt}-\mathrm{size}_3)\cdot w_{1,3}

因此，f_3 的值应为 f_1-\mathrm{size}_3\cdot w_{1,3}+(\mathrm{cnt}-\mathrm{size}_3)\cdot w_{1,3}，即

f_1-w_{1,3}(\mathrm{cnt}-2\cdot\mathrm{size}_3)

归纳： 令该树的原根为 u，新根为 v 且 v\in\operatorname{son}(u)，则状态 f 的转移方程为

f_v=f_{u}-w_{u,v}(\mathrm{cnt}-2\cdot\mathrm{size}_v)

最后，状态 f_i 存储以 i 为集会地点的不方便程度，题目要求最小化不方便程度，因此答案为

\min(f_1,~f_2,~\dots,~f_N)

注：题目数据可能会超过 int，部分变量和数组需要开 long long。

理解了这个，代码不就是手到擒来吗？
洛谷 P2986 Great Cow Gathering G 的完整代码如下：

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e5+5;
vector<pair<int,int>>g[N];
int n,c[N];
long long f[N],size[N],cnt;
long long ans=1e18;
void build(int u,int fa,long long dist){
    size[u]=c[u];
    f[1]+=c[u]*dist;
    for (const auto &e:g[u]){
        int v=e.first,w=e.second;
        if (v==fa) continue;
        build(v,u,dist+w);
        size[u]+=size[v];
    }
}
void dfs(int u,int fa){
    for (const auto &e:g[u]){
        int v=e.first,w=e.second;
        if (v==fa) continue;
        f[v]=f[u]+(cnt-2*size[v])*w;
        dfs(v,u);
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
        scanf("%d",&c[i]);
        cnt+=c[i];
    }
    for (int i=1;i<n;++i){
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        g[a].push_back({b,l});
        g[b].push_back({a,l});
    }
    build(1,0,0);
    dfs(1,0);
    for (int i=1;i<=n;++i) ans=min(ans,f[i]);
    printf("%lld",ans);
    return 0;
}

附录 A：树的基本定理

:::epigraph[声明] 本文的核心思想、推导过程、代码实现及附录证明均由本人独立完成。在撰写过程中，使用了 DeepSeek 对全文的语句通顺度进行润色。 ::: 定义：

总根：整棵树的根节点。
连通分量：在一个无向图中，图内任意两点均存在路径。
子节点集合：对于一个节点 u，\operatorname{son}(u) 表示 u 节点的所有子节点的集合。特别地，若 u 是叶子节点，则 \operatorname{son}(u)=\varnothing。
节点距离：一个节点到根节点的唯一简单路径上所有边的边权之和。
树的距离：所有节点距离之和。
V 和 E：通常代表节点集合和边集合。 ::::info[定理 [1]] 命题： 若一棵树去掉一条边，则必然会将这棵树恰好分割为 2 个连通分量。

证明

已知一棵无向树 T=(V,E)，要去掉一条边 e\in E，设 e=(u,v)。
则去掉 e 后，图 T'=(V,E\setminus e) 恰好被分割为两个连通分量。

由于 T 是树，任意两个顶点之间存在唯一的一条简单路径。
特别地，u 和 v之间的唯一路径就是边 e 本身。在 T' 中，边 e 被移除，因此不存在任何从 u 到 v 的路径，故 u 和 v 属于不同的连通分量。

考虑任意其他节点 a\in V\setminus\{u,v\}。
在树 T 中，a 和 u 有且只有一条简单路径，路径上的所有边组成一个集合，设为 P_{a,u}。

对于 e，分两种情况讨论：

若 e\not\in P_{a,u}，则 P_{a,u}\subseteq T'，故 a 和 u 连通。
若 e\in P_{a,u}，则 e 必为路径的最后一条边，因为 u 是端点，即路径形如 a\to\cdots\to v\to u
在 T' 中 (u,v) 已去除。此时，P_{a,v}=P_{a,u}\setminus e，该路径不包含 e，故 a 与 v 连通。

因此，对于 T' 的任意节点，均只与 u 和 v 中的其中一个相连，又因为 u 和 v 不连通，所以 T' 恰好分成 2 个连通分量，一个包含 u，另一个包含 v。 :::align{right} 证毕 ::: :::: ::::info[定理 [2]] 命题： 若一棵树有 N 个节点，则该树必然有 (N-1) 条边。

证明

考虑从 N 个孤立节点开始构造一棵树，此时每个节点自身构成一个连通分量。
目标：把 N 个连通分量降到 1 个，且不存在自环和重边。此时该图是一棵树。

我们从空图开始构造一棵树。考虑添加边 (u,v)，分两种情况：

若 u,v 原本不在同一个连通分量里，则 (u,v) 就会把这两个分量合并成一个新的连通分量。因此，连通分量的总数会减少 1。
若 u,v 已经在同一个连通分量里，则 (u,v) 会形成一个环，在树中是不允许的。

因此，每添加一条连接不同分量的边，连通分量数减少 1，因此从 N 个分量到 1 个分量恰好需要 (N-1) 次这样的操作。

反之：

若边数 <N-1，则至少剩余 1 个分量未连通，与树的连通性矛盾。
若边数 >N-1，则必然会出现环，与树的无环性矛盾。

综上，若一棵树有 N 个节点，则该树必然有 (N-1) 条边。否则无法构成树。 :::align{right} 证毕 ::: ::::

版权声明

本文采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

您需遵守下列条件：

署名：您必须给出适当的署名，提供指向本许可协议的链接，并标明是否对原始作品作了修改。您可以用任何合理的方式来署名，但不得以任何方式暗示许可人为您或您的使用背书。
非商业性使用：您不得将本作品用于商业目的。
相同方式共享：如果您再混合、转换或者基于本作品进行创作，您必须基于与原先相同的许可协议分发您贡献的作品。

最后，欢迎各位读者引用本文（需注明文章来源和署名），祝您树形 DP 之路一帆风顺！