题解 | #[USACO 2010 Mar G]Great Cow Gathering#

//由于有N-1条路，所以最终是一个双端的树形结构。那么可以任意选择一个点作为根节点。
//那么深搜的话每向下走一步的话该节点以及子节点的的距离就会减去这一段距离，其余节点会加上这一距离。
//也就是说只要顺便选定一个根节点接着向下进行深搜就可以快速得到接下来其他农场的数值。
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int maxn = 100000+10;
struct Nd{
    int next;
    int w;//边上的权重
};
//先用邻接表保存试一试
struct Node {
    //保存相连接的节点
    vector<Nd> v;
    int w;//农场里面的牛数量.
} node[maxn];
int n;
int temp_ans = 0;
int total = 0;
int c[maxn];

void add(int a, int b, int l) {
    node[a].v.push_back(Nd{b, l});
}

int DFS(int x, int fa, int huaf) {
    int num = 0;
    for (int i=0;i<node[x].v.size();i++) {
        int next = node[x].v[i].next;
        if (next!=fa) {
            num += DFS(next, x, node[x].v[i].w);
        }
    }
    num = num+node[x].w;
    temp_ans += (num)*huaf;
    node[x].w = num;
    return num;
}

void DFS2(int x, int fa, int ans) {
    for (int i=0;i<node[x].v.size();i++) {
        int next = node[x].v[i].next;
        if (next!=fa) {
            int temp =  ans + (total-node[next].w)*node[x].v[i].w - node[next].w*node[x].v[i].w;
            temp_ans = min(temp_ans, temp);
            DFS2(next, x, temp);
        }
    }
}

signed main() {
    cin>>n;
    int a, b, l;
    for (int i=1;i<=n;i++) {
        cin>>c[i];
        node[i].w = c[i];
        total += c[i];
    }
    for (int i=1;i<n;i++) {
        cin>>a>>b>>l;
        add(a,b,l);
        add(b, a, l);
    }
    DFS(1, 1, 0);
    DFS2(1, 1, temp_ans);
    cout<<temp_ans;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int maxn = 1000000+10;
struct Edge{
    int to,next, w;//终点，同起点的上一条边的编号,边权。
} edge[maxn];
int head[maxn];
int n;
//c是每个仓里面牛的数量，q是树下的牛的数量总数，dis是花费，其实要的仅仅只是根的总花费。
int c[maxn], q[maxn], dis[maxn], f[maxn];
int cnt = 1;
int tot = 0;
int sum = 0;

void add(int u, int v, int w) {
    edge[cnt] = (Edge) {u, head[v], w};
    head[v] = cnt++;
}

int DFS(int x, int fa) {
    int tot = 0;
    for (int i=head[x];i;i = edge[i].next) {
        if (edge[i].to!=fa) {
            int s = DFS(edge[i].to, x);
            dis[x] += dis[edge[i].to]+edge[i].w*s;
            tot += s;
        }
    }
    //q保存的是每个节点向下的总数量（包括该节点）。
    return q[x] = tot+c[x];
}

void DFS2(int x, int fa) {
    for (int i=head[x];i;i=edge[i].next) {
        if (edge[i].to!=fa) {
            int s = edge[i].w;
            f[edge[i].to] = f[x]-q[edge[i].to]*s+(sum-q[edge[i].to])*s;
            DFS2(edge[i].to, x);
        }
    }
}

signed main() {
    int u, v, w;
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>c[i];
        sum += c[i];
    }
    for (int i=1;i<n;i++) {
        cin>>u>>v>>w;
        add(u, v, w);
        add(v, u, w);
    }
    DFS(1, 1);
    DFS2(1, 1);
    int ans = LONG_LONG_MAX;
    for (int i=1;i<=n;i++) {
        ans = min(ans, f[i]);
    }
    cout<<ans+dis[1];
    return 0;
}