[算法汇总]树形dp
Nickel_Angel
2019-10-04 21:20:04
前几天本来写了一些背包题，但刷完才发现大部分都是树形 dp……特此写一下总结QwQ
***
## Part 0 前置知识
### $\circ$ Main idea
树形 dp 的状态设计一般有两种：
有一些题目要求我们在树上选择一些特殊点，并统计满足某些特定条件时的方案数等……
这时可以考虑**节点选择法**：$dp[u][0 / 1]$ 表示 $u$ 节点选或不选两种状态。
有一些题目树上的点有点权，每个节点可以向它的父亲节点上传一些点权，同时要满足一些限制，并求出最小或最大代价。
这时可以考虑**树形背包法**：$dp[u][k]$ 表示以 $u$ 为节点的子树上传权值的状态。
### $\circ$ 刷表法 & 填表法
这两种方法在 dp 转移实现很常见，虽然它们有很大的差别，但总是会被忽视。
填表法主要是用一个状态转移多个状态，而刷表法是用多个状态转移到一个状态。
注意刷表法即 01 背包问题的 dp 转移方法，故一般需要倒序枚举。
## Part 1 树形背包
[P1273 有线电视网](https://www.luogu.org/problem/P1273)
看到本题显然是一个树形 dp，发现有线电视网只有在叶节点可以有收入，故考虑将答案以某种形式向上合并至根节点。而合并方式就是树形 dp 。
题目中说道：
> 有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
这正启发了我们如何设计状态，我们可以设 $dp[u][i]$ 为以 $u$ 为根的子树内满足 $i$ 个客户的需求所能获得的最大利润。不难发现对于一个节点 $u$ 来说有转移：
$$
dp[u][i] = \min_{v \in son(u),j = 1}^{i}(dp[u][i - j] + dp[v][j] - cost(u,v))
$$
（其中 $son(u)$ 是 $u$ 的孩子集合，$cost(u, v)$ 是 $(u, v)$ 这条边的花费）
不妨将以上转移看做一个背包：将每个用户看做一个物品，将 $u$ 节点的每个儿子子树内的用户看做一组物品。故其本质上是一个分组背包。
上方的方程即：对于 $u$ 的每个孩子结点 $v$ 枚举一个 $j$，令其对 $u$ 为根的子树内满足的 $i$ 个客户做出 $j$ 个客户的贡献，剩下的 $i - j$ 个客户交给节点 $u$ 的其他儿子。而由于经过 $(u,v)$ 这条边需要花费 $cost(u, v)$，故应减去对应的花费。我们发现 $dp[u][0]$ 对答案不会造成任何影响，故 $j$ 可以从 $1$ 开始枚举。
注意由于我们转移时枚举 $u$ 节点的孩子 $v$ 是按照先后顺序枚举的，故每当枚举一个新的孩子时，我们采用的是刷表法更新数组，故应倒序枚举 $i$ ，就像 01 背包那样刷表枚举体积一样。
转移起始位置为叶子节点，即若 $u$ 为叶子节点，根据我们设计的状态，有 $dp[u][1] = money[u]$ （$money[u]$ 即为该节点的客户支付的费用）。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
namespace Primary
{
int n, m, head[3010], to[3010], val[3010], next[3010], tot = 1;
int dp[3010][3010], key[3010], money[3010];
inline void add_edge(int u, int v, int w)
{
to[++tot] = v;
val[tot] = w;
next[tot] = head[u];
head[u] = tot;
}
void dfs(int u)
{
if (u > n - m)
{
key[u] = 1;
dp[u][1] = money[u];
return;
}
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
dfs(v);
key[u] += key[v];//key 数组记录的是当前节点子树内的叶子节点个数
for (int i = key[u]; i >= 0; --i)
{
for (int j = 1; j <= key[v]; ++j)
//考虑到 key[v] 可能小于 i,故可以将枚举上界化为 key[v] 从而减少无用转移
{
if (i >= j)
dp[u][i] = max(dp[u][i], dp[u][i - j] + dp[v][j] - val[c]);
}
}
}
}
void main()
{
scanf("%d%d", &n, &m);
memset(dp, -0x3f, sizeof(dp));
for (int i = 1, size; i <= n - m; ++i)
{
dp[i][0] = 0;
scanf("%d", &size);
for (int j = 1, v, w; j <= size; ++j)
{
scanf("%d%d", &v, &w);
add_edge(i, v, w);
}
}
for (int i = n - m + 1; i <= n; ++i)
scanf("%d", money + i);
dfs(1);
for (int i = m; i >= 0; --i)
{
if (dp[1][i] >= 0)
{
printf("%d\n", i);
break;
}
}
}
}
int main()
{
Primary::main();
return 0;
}
```
[P3177 [HAOI2015]树上染色](https://www.luogu.org/problem/P3177)
考虑效仿上题一样设计状态：设 $dp[u][i]$ 表明以 $u$ 节点的子树中选了 $i$ 个节点染成黑色的收益。
显然方程与上题相似，均为：
$$
dp[u][i] = \min_{v \in son(u),j = 0}^{i}(dp[u][i - j] + dp[v][j] + val(u,v))
$$
这里 $val(u,v)$ 为 $(u,v)$ 这条边对答案的贡献，我们设 $size[v]$ 为以 $v$ 为根的子树内总共有多少个点，$w(u,v )$ 为这条边的边权，考虑如何计算贡献。
分别考虑黑白两色节点的贡献，不难发现若 $v$ 的子树内有 $j$ 个节点为黑色，则子树外就有 $k - j$ 个节点为黑色，故黑色节点在这条边上的贡献为 $w(u, v) \times j \times (k - j)$，同理，$v$ 的子树内就有 $size[v] - j$ 个节点为白色，则子树外有 $n - k - (size[v] - j)$ 个节点为白色，故白色节点对于这条边的贡献为 $(size[v] - j) \times (n - k + j - size[v]) \times w$，而黑色节点与白色节点在这条边上贡献之和即为这条边对答案的总贡献。
```cpp
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
namespace Primary
{
int n, k, size[2010], head[2010], to[4010], next[4010], val[4010], tot = 1;
long long dp[2010][2010];
inline void add_edge(int u, int v, int w)
{
to[++tot] = v;
val[tot] = w;
next[tot] = head[u];
head[u] = tot;
}
void dfs(int u, int pre)
{
size[u] = 1;
dp[u][0] = dp[u][1] = 0;
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
if (v == pre) continue;
dfs(v, u);
size[u] += size[v];
}
for (int c = head[u], v, w; c; c = next[c])
{
v = to[c], w = val[c];
if (v == pre) continue;
for (int i = min(k, size[u]); i >= 0; --i)
{
for (int j = 0; j <= min(i, size[v]); ++j)
{
if (dp[u][i - j] == -1) continue;
long long val = 1ll * j * (k - j) * w +
1ll * (size[v] - j) * (n - k + j - size[v]) * w;
dp[u][i] = max(dp[u][i], dp[u][i - j] + dp[v][j] + val);
}
}
}
}
void main()
{
scanf("%d%d", &n, &k);
for (int i = 1, u, v, w; i < n; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w), add_edge(v, u, w);
}
memset(dp, -1, sizeof(dp));
dfs(1, 0);
printf("%lld", dp[1][k]);
}
}
int main()
{
Primary::main();
return 0;
}
```
[P4037 [JSOI2008]魔兽地图](https://www.luogu.org/problem/P4037)
本题的树形 dp 有两种限制，一是数量限制，二是金币数限制，考虑将它们都设计进状态：设 $f[u][i][j]$ 为向上贡献 $i$ 个 $u$ 号装备用于合成，且在其子树内花费为 $j$ 得到的最大力量值。
为了方便，我们用 $cost[u]$ 表示 $u$ 的单价，$limit[u]$ 为 $u$ 的数量限制，$p[u]$ 为 $u$ 的力量值，若 $v$ 为比 $u$ 高一级的装备，$w(u,v)$ 表示合成 $v$ 需要的 $u$ 的个数。
对于低级装备 $u$ 来说，转移显然为：
$$
f[u][i][j \times cost[u]] = p[u] \times (j - i)
$$
而对于高级装备 $u$ 来说，首先合成一个 $u$ 的花费为 $cost[u] = \sum_{v \in son(u)} cost[v] \times w(u, v)$ 。
考虑枚举合成 $u$ 装备的数量 $i$，首先计算出此时在 $u$ 子树内花费为 $j$ 时所获得的最大力量值 $g[j]$，有转移：
$$
g[j] = \max_{v \in son(u), k = 0}^j (f[v][i \times w(u, v)][k])
$$
注意这里跟上文的背包一样 $j$ 是倒序枚举转移的，并且注意如果我们合成一个 $u$ 装备需要使其所有子节点的装备数量均满足要求，故我们在转移时不能直接将其写作：
```cpp
g[j] = max(g[j], f[v][i * val[c]][k]);
```
如果 $g[j]$ 在没考虑 $v$ 这个子节点之前比较大，超过了 $f[v][i \times w(u, v)][k]$ 的最大值，那么在枚举节点 $v$ 时，它就不会被更新，这样就相当于没有考虑到 $v$ 这个子节点，导致转移出错。故考虑用中间变量求出 $f[v][i \times w(u, v)][k]$ 的最大值，最后强制更新 $g[j]$ 。
然后我们在计算出若向上贡献 $j$ 个 $u$ 号装备用于合成，花费为 $k$ 时所获得的最大力量值。有转移：
$$
f[u][j][k] = max(g[k] + p[u] \times (i - j))
$$
注意到给出的图可能为森林，故在树形 dp 后，还要用分组背包求一遍答案。
```cpp
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
namespace IO
{
template<typename T>
inline void input(T &x)
{
x = 0;
register char ch = getchar();
register bool f = false;
while (!isdigit(ch))
{
f |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = f ? -x : x;
}
}
using namespace IO;
namespace Primary
{
const int inf = 0x3f3f3f3f;
int n, m, in[60];
int head[60], to[20010], val[20010], next[20010], tot = 1;
int p[60], limit[60], cost[60], f[60][110][2010], g[2010], dp[2010];
bool vis[60];
inline void add_edge(int u, int v, int w)
{
to[++tot] = v;
val[tot] = w;
next[tot] = head[u];
head[u] = tot;
++in[v];
}
void dfs(int u)
{
if (vis[u]) return;
vis[u] = true;
if (!head[u])
{
limit[u] = min(limit[u], m / cost[u]);//limit[u] 还需考虑是否能买这么多
for (int i = limit[u]; i >= 0; --i)
{
for (int j = i; j <= limit[u]; ++j)
{
f[u][i][j * cost[u]] = p[u] * (j - i);
}
}
return;
}
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
dfs(v);
limit[u] = min(limit[u], limit[v] / val[c]);//limit 的更新
cost[u] += val[c] * cost[v];
}
limit[u] = min(limit[u], m / cost[u]);
for (int i = limit[u]; i >= 0; --i)
{
memset(g, -0x3f, sizeof(g));//g 初始化
g[0] = 0;
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
for (int j = m; j >= 0; --j)
{
int t = -inf;
for (int k = 0; k <= j; ++k)
{
t = max(t, g[j - k] + f[v][i * val[c]][k]);//中间变量求出最大值
}
g[j] = t;//强制转移
}
}
for (int j = 0; j <= i; ++j)
{
for (int k = 0; k <= m; ++k)
{
f[u][j][k] = max(f[u][j][k], g[k] + p[u] * (i - j));
}
}
}
}
void main()
{
input(n), input(m);
memset(limit, 0x3f, sizeof(limit));
for (int i = 1; i <= n; ++i)
{
input(p[i]);
char type = getchar();
while (!isalpha(type)) type = getchar();
if (type == 'A')
{
int x, u, w;
input(x);
for (int j = 1; j <= x; ++j)
{
input(u), input(w);
add_edge(i, u, w);
}
}
else
{
input(cost[i]);
input(limit[i]);
}
}
memset(f, -0x3f, sizeof(f));
for (int i = 1; i <= n; ++i)
{
if (in[i]) continue;
dfs(i);
for (int j = m; j >= 0; --j)//外层为分组背包
{
for (int k = 0; k <= j; ++k)
{
dp[j] = max(dp[j], dp[j - k] + f[i][0][k]);
}
}
}
printf("%d\n", dp[m]);
}
}
int main()
{
Primary::main();
return 0;
}
```
## Part 2 节点选择
[P1352 没有上司的舞会](https://www.luogu.org/problem/P1352)
本题是求树的最大独立权集，由于一个人对答案是否会对答案产生贡献取决于其是否会参加舞会，故考虑根据每个人是否会参加舞会设计状态。
设 $dp[u][0]$ 为在 $u$ 为首的子树中，$u$ 不参加舞会的最大快乐值，$dp[u][1]$ 为在 $u$ 为首的子树中，$u$ 参加舞会的最大快乐值。
考虑转移，若 $u$ 参加舞会，则其子节点不能参加舞会：
$$
dp[u][1] = \sum_{v \in son(u)} dp[v][0]
$$
若 $u$ 不参加舞会，则其子节点参不参加舞会均可，我们这时取最优的即可：
$$
dp[u][0] = \sum_{v \in son(u)} max(dp[v][0], dp[v][1])
$$
注意边界：$dp[u][0] = 0, dp[u][1] = w[u]$ 。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
namespace Primary
{
int n, w[6010], dp[6010][2], in[6010];
int head[6010], to[6010], next[6010], tot = 1;
inline void add_edge(int u, int v)
{
to[++tot] = v;
next[tot] = head[u];
head[u] = tot;
}
void dfs(int u)
{
dp[u][0] = 0, dp[u][1] = w[u];
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
dfs(v);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
void main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", w + i);
for (int i = 1, u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
add_edge(v, u);
++in[u];
}
int root = 0;
for (int i = 1; i <= n; ++i)
{
if (!in[i])
{
root = i;
break;
}
}
dfs(root);
printf("%d\n", max(dp[root][0], dp[root][1]));
}
}
int main()
{
Primary::main();
return 0;
}
```
[P4362 [NOI2002]贪吃的九头龙](https://www.luogu.org/problem/P4362)
本题由于对于大头吃的果子数量有限制，故考虑将大头吃的果子数量设计进状态，设 $dp[u][i]$ 为 $u$ 子树内的果子其中有 $i$ 个是大头吃的的最小难受值。但由于一条边对答案是否有贡献取决于这条边的两个端点是否被一个头吃，并且我们发现若将一个节点具体是被哪个头吃设计进状态复杂度不够优秀。
考虑优化，我们进一步发现我们只用关心一个节点的果子是否是大头吃的即可。考虑 $m > 2$ 时，若有一个方案使得两个直接相连的点被同一个小头吃了，我们总能通过调整使得这两个点被不同小头吃掉。而 $m = 2$ 时，一个节点不是被大头吃就是被小头吃。故我们直接用 $dp[u][i][0/1]$ 表示 $u$ 子树内的果子其中有 $i$ 个是大头吃的，且 $u$ 这个果子是被小头 / 大头吃的的最小难受值。
考虑转移，首先 $u$ 的每个子节点有两种选择，被小头吃或被大头吃，我们只需考虑这两种情况，然后像树形背包那样转移即可。但对于 $f[v][j][0] \rightarrow f[u][i][0]$ 的转移来说，还需考虑到若 $m = 2$ 则两个点只能被同一个小头吃，这时需要计算上这条边的贡献。
$$
\begin{aligned} f[u][i][0] &= \min_{v \in son(u), j = 0}^i (dp[v][j][0] + dp[u][i - j][0] + [m = 2] \times w(u, v), dp[v][j][1] + dp[u][i - j][0]) \\f[u][i][1] &= \min_{v \in son(u), j = 0}^i (dp[v][j][1] + dp[u][i - j][1] + w(u, v), dp[v][j][0] + dp[u][i - j][1]) \end{aligned}
$$
注意到转移时是由 $dp[u][i - j][0 / 1]$ 向 $dp[u][i][0 / 1]$ 转移，而 $dp[u][i - j][0 / 1]$ 会先被更新，如果不做任何处理，$dp[u][i][0 / 1]$ 可能会被更新成一个很小的值，显然这样转移是错误的，而又因为 $j$ 从 $0$ 开始，状态可能自己更新自己，故我们也不可以用倒序枚举的方法解决该问题。故我们每次转移前将上次转移得到的值备份一份，这样就不会有后顾之忧了。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cctype>
using namespace std;
template<typename T>
inline bool chkmin(T &x, const T &y) {return x > y ? (x = y, true) : false;}
namespace Primary
{
int n, m, k, head[310], to[610], next[610], val[610], tot = 1;
int dp[310][310][2], rec[310][2];
inline void add_edge(int u, int v, int w)
{
to[++tot] = v;
val[tot] = w;
next[tot] = head[u];
head[u] = tot;
}
void dfs(int u, int pre)
{
dp[u][0][0] = dp[u][1][1] = 0;
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
if (v == pre) continue;
dfs(v, u);
memcpy(rec, dp[u], sizeof(dp[u]));//备份一份 dp 数组
memset(dp[u], 0x3f, sizeof(dp[u]));
for (int i = 0; i <= k; ++i)
{
for (int j = 0; j <= i; ++j)
{
chkmin(dp[u][i][0], min(dp[v][j][0] + rec[i - j][0] +
(m == 2) * val[c], dp[v][j][1] + rec[i - j][0]));
chkmin(dp[u][i][1], min(dp[v][j][1] + rec[i - j][1] + val[c],
dp[v][j][0] + rec[i - j][1]));
}
}
}
}
void main()
{
scanf("%d%d%d", &n, &m, &k);
if (n - k < m - 1)//判断无解
{
puts("-1");
return;
}
for (int i = 1, u, v, w; i < n; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w), add_edge(v, u, w);
}
memset(dp, 0x3f, sizeof(dp));
dfs(1, 0);
printf("%d\n", dp[1][k][1]);
}
}
int main()
{
Primary::main();
return 0;
}
```
[P3354 [IOI2005]Riv 河流](https://www.luogu.org/problem/P3354)
首先通过前面的铺垫，很容易考虑到的是设 $dp[u][i]$ 表明以 $u$ 为根的子树内有 $i$ 个伐木场的最小花费。但下面却出现了问题：对于某些在 $u$ 子树内没有被这 $i$ 个伐木场覆盖的点，其一定会被 $u$ 的某个祖先上的伐木场覆盖，但我们无法得知这个祖先是谁。故考虑将 $u$ 的祖先中，建有伐木场且离 $u$ 最近的节点设计进状态。
故状态最终为：$dp[u][anc][i]$ 表明以 $u$ 为根的子树内建有 $i$ 个伐木场，且离 $u$ 最近的建有伐木场的祖先为 $anc$ 时的最小花费。（注意这里 $u$ 的祖先包含 $u$ 本身）
考虑对于每个节点的子节点对它的贡献：
$$
f[u][anc][i] = \min_{v \in son(u),j = 0}^{i} (f[u][anc][i - j] + f[v][anc][j])
$$
我们考虑将每个点的花费集中到我们枚举的 $anc$ 上，而对于每个节点来说，有在这个节点建伐木场和不在这个节点建伐木场的区别，故转移为：
$$
f[u][anc][i] = \begin{cases} min(f[u][anc][i] + w[u] \times (dis[u] - dis[anc]), f[u][u][i - 1]) & \text{ if $i > 0$} \\ f[u][anc][i] + w[u] \times (dis[u] - dis[anc]) & \text{ if $i = 0$} \end{cases}
$$
注意在 $i > 0$ 的转移时，由于我们在先前考虑 $u$ 每个子节点对其的贡献时，$f[u][u][i]$ 这个状态是没有计算上 $u$ 处的伐木场的，故其实本状态 $u$ 的子树内其实有 $i + 1$ 个伐木场。进而我们在转移时需用 $f[u][u][i - 1]$ 更新 $f[u][anc][i]$ 。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T>
inline bool chkmin(T& x, const T& y) {return x > y ? (x = y, true) : false;}
namespace Primary
{
int n, m, w[110], dis[110], s[110], top = 0;
int head[110], to[110], next[110], val[110], tot = 1;
int f[110][110][60];
inline void add_edge(int u, int v, int w)
{
to[++tot] = v;
val[tot] = w;
next[tot] = head[u];
head[u] = tot;
}
void dfs(int u)
{
s[++top] = u;//我们开一个栈来记录 u 的祖先
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
dis[v] = dis[u] + val[c];
dfs(v);
for (int i = 1; i <= top; ++i)
{
for (int j = m; j >= 0; --j)
{
f[u][s[i]][j] += f[v][s[i]][0];
for (int k = 1; k <= j; ++k)
chkmin(f[u][s[i]][j], f[u][s[i]][j - k] + f[v][s[i]][k]);
}
}
}
for (int i = 1; i <= top; ++i)
{
for (int j = m; j >= 1; --j)
{
f[u][s[i]][j] = min(f[u][s[i]][j] + w[u] * (dis[u] - dis[s[i]]),
f[u][u][j - 1]);
}
f[u][s[i]][0] += w[u] * (dis[u] - dis[s[i]]);
}
--top;
}
void main()
{
scanf("%d%d", &n, &m);
for (int i = 1, fa, d; i <= n; ++i)
{
scanf("%d%d%d", w + i, &fa, &d);
add_edge(fa, i, d);
}
dfs(0);
printf("%d\n", f[0][0][m]);
}
}
int main()
{
Primary::main();
return 0;
}
```
## Part 3 二次扫描与换根法
[P2986 [USACO10MAR]伟大的奶牛聚集](https://www.luogu.org/problem/P2986)
本题要求选择一个节点 $root$ 为根节点，设 $dis_i$ 为 $root$ 到 $i$ 号节点的距离，使得 $\sum_{i = 1}^n dis_i \times c_i$ 最小。
显然如果确定了根节点 $u$，我们可以通过一次树形 dp 算出 $root$ 作为根节点时的答案：
$$
C[u] = \sum_{v \in son(u)} C[v] \text{ (initially $C[u] = c[u]$)}
$$
$$
f[u] = \sum_{v \in son(u)} f[v] + C[v] \times w(u, v)
$$
故考虑将每个点作为根节点计算答案后取其中最小的答案，但这样复杂度是 $O(n^2)$ 的，无法通过本题。
考虑我们是否可以先以任意节点为根节点进行一次树形 dp，用本次得到 $f$ 的值直接计算得到其他节点作为根节点时的答案呢 QwQ？
我们考虑树上的一条边 $(u, v)$，我们假设 $u$ 为 $v$ 的父节点，且我们已计算 $u$ 为根时的答案，我们设节点 $i$ 为根时的答案为 $g[i]$ 。我们考虑 $g[u]$ 和 $g[v]$ 之间有什么微妙的关系。当根节点从 $u$ 变到 $v$ 时，原来 $v$ 的子树内所有节点对答案的贡献减少了 $w(u, v) \times C[v]$，而除 $v$ 子树外的所有节点对答案的贡献增加了 $w(u, v) \times (sum - C[v])$（其中 $sum$ 是所有节点 $c_i$ 的和，即牛的总数）。
故 $g$ 的转移为：
$$
\begin{aligned}g[u] &= g[fa[u]] - w(u, fa[u]) \times C[v] + w(u, fa[u]) \times (sum - C[v]) \\ &= g[fa[u]] + w(u, fa[u]) \times (sum - 2 \times C[v]) \end{aligned}
$$
这样我们就可以在 $O(n)$ 的时间内求解该问题了。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
namespace Primary
{
const int maxn = 1e5 + 10;
int n, head[maxn], to[maxn << 1], next[maxn << 1], val[maxn << 1], tot = 1;
ll ans = 0, sum = 0, f[maxn], C[maxn], g[maxn];
inline void add_edge(int u, int v, int w)
{
to[++tot] = v;
val[tot] = w;
next[tot] = head[u];
head[u] = tot;
}
void dfs_init(int u, int pre)
{
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
if (v == pre) continue;
dfs_init(v, u);
C[u] += C[v];
f[u] += f[v] + C[v] * val[c];
}
}
void dfs_solve(int u, int pre)
{
ans = min(ans, g[u]);
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
if (v == pre) continue;
g[v] = g[u] + val[c] * (sum - 2 * C[v]);
dfs_solve(v, u);
}
}
void main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%lld", C + i);
sum += C[i];
}
for (int i = 1, u, v, w; i < n; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w), add_edge(v, u, w);
}
dfs_init(1, 0);
ans = g[1] = f[1];
dfs_solve(1, 0);
printf("%lld\n", ans);
}
}
int main()
{
Primary::main();
return 0;
}
```