【树形dp题解】dfs的巧妙应用

【树形dp题解】dfs的巧妙应用

[P2986 USACO10MAR] Great Cow Gathering G - 洛谷

• 题目大意：

  Bessie 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。

  每个奶牛居住在 $N$ 个农场中的一个，这些农场由 $N-1$ 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 $i$ 连接农场 $A_i$ 和 $B_i$，长度为 $L_i$。集会可以在 $N$ 个农场中的任意一个举行。另外，每个牛棚中居住着 $C_i$ 只奶牛。

  在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 $X$ 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 $i$ 到达农场 $X$ 的距离是 $20$，那么总路程就是 $C_i\times 20$）。帮助 Bessie 找出最方便的地点来举行大集会。

对于$dfs$来说，我们可以从上到下计算，也可以从下到上计算。如果我们想知道每个节点距离根节点的距离$d_i(i\ne root)$，那么我们不妨令$d_{root}=0$，通过自顶向下的搜索得到$d_i(i\ne root)$

不妨设$s{z}_i$表示以$i$为根的子树中奶牛数量的和。此时需要自底向上计算

不妨设$f_i$表示以节点$i$为聚会地点时的最小不方便程度。对于以$i$为根时树的叶子节点来说，$f_i=d_i\times C_i(i=叶子节点)$。对于以$i$为根，非叶子节点的节点来说，$f_i=f_j+d_i\times C_i(i\ne 叶子节点,j是节点i的儿子节点)$。这可以从底向上计算得到

读者不妨认真体会以下代码。我给出一些理解：在自底向上计算时，一般先处理本层逻辑，在回溯时累加

由于此题可以任选根节点进行$dfs$，这里我选择$1$作为根节点

void dfs1(int u, int fa) {sz[u] = cnt[u];f[u] = d[u] * cnt[u];for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j == fa) continue;d[j] = d[u] + w[i];dfs1(j, u);sz[u] += sz[j];f[u] += f[j];}
}

在预处理好上述含义数组后，我们思考转移方程。读者不妨画出图来，否则难以理解

假设根节点$u$的儿子有$so{n}_1,so{n}_2$，若此时将$so{n}_1$作为集会地点，$f[so{n}_1]$可以$f[u]$转移得到

转换集会地点前：$f[u]=f[so{n}_1]+f[so{n}_2]$

转换地点后：$f[so{n}_1]$本来以根节点$1$为集会地点，现在集会地点变为$j(j是根节点的儿子)$，转换后有$f[so{n}_1]=f[so{n}_1]-w[i]\times sz[so{n}_1]$

同理，$f[so{n}_2]=f[so{n}_2]+w[i]\times (sz[1]-sz[so{n}_1])$

有$f[j]=f[so{n}_1]-w[i]\times sz[so{n}_1]+f[so{n}_2]+w[i]\times (sz[1]-sz[so{n}_1])$

即$f[j]=f[so{n}_1]+f[so{n}_2]-w[i]\times (2sz[so{n}_1]-sz[1])=f[u]-w[i]\times (2sz[so{n}_1]-sz[1])$

void dfs2(int u, int fa) {for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j == fa) continue;f[j] = f[u] - (2 * sz[j] - sz[1]) * w[i];dfs2(j, u);}
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl "\n"#define int long longconst int N = 100010, M = N * 2;
int h[N], e[M], ne[M], w[M], idx;
int cnt[N];
int n;
int res = INT_MAX;
int d[N], sz[N], f[N];void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}void dfs1(int u, int fa) {sz[u] = cnt[u];f[u] = d[u] * cnt[u];for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j == fa) continue;d[j] = d[u] + w[i];dfs1(j, u);sz[u] += sz[j];f[u] += f[j];}
}void dfs2(int u, int fa) {for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j == fa) continue;f[j] = f[u] - (2 * sz[j] - sz[1]) * w[i];dfs2(j, u);}
}signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);memset(h, -1, sizeof h);cin >> n;for (int i = 1; i <= n; i ++) {cin >> cnt[i];}for (int i = 1; i <= n - 1; i ++) {int u, v, x;cin >> u >> v >> x;add(u, v, x);add(v, u, x);}dfs1(1, -1);dfs2(1, -1);LL res = 1e18;for (int i = 1; i <= n; i ++) {res = min(res, f[i]);}cout << res << endl;return 0;
}