洛谷题单指南-树与图上的动态规划-P2986 [USACO10MAR] Great Cow Gathering G

原题链接：https://www.luogu.com.cn/problem/P2986

题意解读：一棵树中，边权是距离，点权是人数，找到一个点到所有人距离之和最小，求这个最小距离和。

解题思路：

换根DP的典型题，思路可以参考：https://www.cnblogs.com/hackerchef/p/18075408

核心就是两次DFS：

1、第一次DFS，求f[1]：1到所有人距离之和，计算每个点i为根的子树大小sz[i]

2、第二次DFS，对于边u->v，通过f[u]递推f[v]，这里面的转换关系根据参考题解中的内容容易得出

100分代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100005, M = 200005;

int c[N];
int head[N], to[M], w[M], nxt[M], idx;
LL f[N]; //f[i]表示所有牛到i点的距离之和
int sz[N]; //sz[i]表示以i为根的子树大小
int n;

void add(int a, int b, int c)
{
    to[++idx] = b;
    w[idx] = c;
    nxt[idx] = head[a];
    head[a] = idx;
}

void dfs1(int u, int fa, int dist)
{
    f[1] += 1ll * c[u] * dist;
    sz[u] = c[u];
    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == fa) continue;
        dfs1(v, u, dist + w[i]);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int fa, int dist)
{
    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == fa) continue;
        f[v] = f[u] - 1ll * sz[v] * w[i] + 1ll * (sz[1] - sz[v]) * w[i];
        dfs2(v, u, dist + w[i]);
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i < n; i++)
    {
        int a, b, l;
        cin >> a >> b >> l;
        add(a, b, l), add(b, a, l);
    }

    dfs1(1, 0, 0);
    dfs2(1, 0, 0);

    LL ans = LLONG_MAX;
    for(int i = 1; i <= n; i++) ans = min(ans, f[i]);
    cout << ans;
    return 0;
}