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 找出最方便的地点来举行大集会。

输入格式

第一行一个整数 $N$ 。

第二到 $N+1$ 行：第 $i+1$ 行有一个整数 $C_i$。

第 $N+2$ 行到 $2N$ 行：第 $i+N+1$ 行为 $3$ 个整数：$A_i,B_i$ 和 $L_i$。

输出格式

一行一个整数，表示最小的不方便值。

输入输出样例 #1

输入 #1

5 
1 
1 
0 
0 
2 
1 3 1 
2 3 2 
3 4 3 
4 5 3

输出 #1

15

说明/提示

$1\le N\le 10^5$，$1\le A_i\le B_i\le N$，$0\le C_i,L_i\le 10^3$。
【分析】
代码解释
1、输入处理：

读取农场数量 N。

读取每个农场的奶牛数量 C[i]。

读取道路信息，构建邻接表 adj。

2、第一次 DFS (dfs1)：

计算以每个节点 u 为根的子树中的 dp[u] 和 size[u]。

dp[u] 表示以 u 为根的子树中，所有奶牛到 u 的总路程。

size[u] 表示以 u 为根的子树中，奶牛的总数量。

3、第二次 DFS (dfs2)：

通过换根 DP 计算每个节点作为集会地点时的不方便值。

换根公式：dp[v] = dp[u] - size[v] * L + (size[1] - size[v]) * L。

更新最小不方便值 min_inconvenience。

4、输出结果：

输出最小的不方便值。

//【参考代码】
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 5;

vector<pair<int, int>> adj[MAXN]; // 邻接表存储树
ll dp[MAXN]; // dp[u]: 以 u 为根的子树中，所有奶牛到 u 的总路程
ll size[MAXN]; // size[u]: 以 u 为根的子树中，奶牛的总数量
ll C[MAXN]; // C[u]: 节点 u 的奶牛数量
ll min_inconvenience = 1e18; // 最小不方便值

// 第一次 DFS，计算 dp[u] 和 size[u]
void dfs1(int u, int parent) {
    size[u] = C[u];
    for (int i = 0; i < adj[u].size(); i++) { // 使用标准 for 循环
        int v = adj[u][i].first;
        int L = adj[u][i].second;
        if (v == parent) continue;
        dfs1(v, u);
        size[u] += size[v];
        dp[u] += dp[v] + size[v] * L;
    }
}

// 第二次 DFS，换根 DP，计算每个节点作为集会地点时的不方便值
void dfs2(int u, int parent) {
    min_inconvenience = min(min_inconvenience, dp[u]);
    for (int i = 0; i < adj[u].size(); i++) { // 使用标准 for 循环
        int v = adj[u][i].first;
        int L = adj[u][i].second;
        if (v == parent) continue;
        // 换根操作
        dp[v] = dp[u] - size[v] * L + (size[1] - size[v]) * L;
        dfs2(v, u);
    }
}

int main() {
    int N;
    cin >> N;

    // 输入每个农场的奶牛数量
    for (int i = 1; i <= N; i++) { // 使用标准 for 循环
        cin >> C[i];
    }

    // 输入道路信息，构建邻接表
    for (int i = 1; i <= N - 1; i++) { // 使用标准 for 循环
        int A, B, L;
        cin >> A >> B >> L;
        adj[A].push_back({B, L});
        adj[B].push_back({A, L});
    }

    // 第一次 DFS，计算 dp 和 size
    dfs1(1, -1);

    // 第二次 DFS，换根 DP，计算最小不方便值
    dfs2(1, -1);

    // 输出结果
    cout << min_inconvenience << endl;

    return 0;
}