洛谷 P2986 USACO10MAR Great Cow Gathering G

url: https://www.luogu.com.cn/problem/P2986

tag:
动态规划，树形DP，USACO，2010

思路：
可以参考 洛谷P3478 POI 2008 STA-Station 都是要求出当某一个节点为根时其他点到这个根的距离，我们可以用一次dfs来求出以任意选的一个节点作为根节点时的答案，比如选择节点1为根节点。然后再利用一次dfs来做节点转移的更新，求当其他节点做根节点时的答案，然后和全局答案做一个更新。最后输出这个答案即可。对于这道题，状态转移方程1是 f[u] += f[j] + w[i] * s[j]; 用f[i] 表示以i为根节点时其他节点到该点的不方便值。状态转移方程2是 d[j] = d[u] - s[j] * w[i] + (cnt - s[j]) * w[i]; 先做初始化让 d[1] = f[1] 然后自上到下更新。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int e[N * 2], ne[N * 2], h[N], w[N * 2], idx;
int n;
LL cnt, ans;
int c[N];
LL f[N];
LL s[N];
LL d[N];
void add(int a, int b, int cc)
{
    e[idx] = b;
    w[idx] = cc;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs1(int u, int fa)
{
    s[u] = c[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs1(j, u);
        s[u] += s[j];
        f[u] += f[j] + w[i] * s[j];
    }
}
void dfs2(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        d[j] = d[u] - s[j] * w[i] + (cnt - s[j]) * w[i];
        ans = min(ans, d[j]);
        dfs2(j, u);
    }
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++) cin >> c[i], cnt += c[i];
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b, cc;
        cin >> a >> b >> cc;
        add(a, b, cc), add(b, a, cc);
    }
    dfs1(1, 0);
    d[1] = f[1];
    ans = d[1];
    dfs2(1, 0);
    cout << ans << endl;
    return 0;
}