Skip to content

「USACO 2010 March (Gold)」Great Cow Gathering

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

每个奶牛居住在 NN 个农场中的一个,这些农场由 N1N - 1 条道路连接,并且从任意一个农场都能够到达另外一个农场。道路 ii 连接农场 AiA_iBiB_i,长度为 LiL_i。集会可以在 NN 个农场中的任意一个举行。另外,每个牛棚中居住着 CiC_i 只奶牛。

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

#输入格式

第一行一个整数 NN

第二到 N+1N + 1 行:第 i+1i + 1 行有一个整数 CiC_i

N+2N+2 行到 2N2N 行:第 i+N+1i + N + 1 行为 33 个整数:Ai,BiA_i, B_iLiL_i

#输出格式

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

#输入输出样例

样例输入 #1

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

样例输出 #1

15

#提示

对于 100%100\% 的数据,1N1051 \leq N \leq 10^51AiBiN1 \leq A_i \leq B_i \leq N0Ci,Li1030 \leq C_i, L_i \leq 10^3

#思路

为一棵无根树指定根节点使得所有点的深度之和最小。

可以发现选定农场沿某条边 uwvu \overset{w}{\to} v 移动时,uu 所在子树中的所有奶牛对答案的贡献都会增加 wwvv 所在子树中的所有奶牛对答案的贡献都会减少 ww,答案的增加量为 w(size(u)size(v))w (\mathrm{size}(u) - \mathrm{size}(v))。显然当选定农场位于树的重心时,答案为最小值(准确来说,应该将树的重心的定义中「最大子树的节点数最少」改为「最大的点权块最小」才成立)。

于是求树的重心的代码变成了这样(注意高亮行):

14
15
16
17
18
19
void dfs1(int u, int f) {
siz[u] = c[u];

for (auto e : g[u]) {
int v = e.first,
w = e.second;

最后求深度时不要忘了加上边权:

void dfs2(int, int) 中:
34
35
36
37
38
39
40
41
    int v = e.first,
w = e.second;

if (v == f) continue;

dep[v] = dep[u] + w;
dfs2(v, u);
}

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, sum, root, c[N], siz[N], max_siz[N], dep[N];
long long ans;
std::vector<std::pair<int, int>> g[N];

void dfs1(int u, int f) {
siz[u] = c[u];

for (auto e : g[u]) {
int v = e.first,
w = e.second;

if (v == f) continue;

dfs1(v, u);

siz[u] += siz[v];
max_siz[u] = std::max(max_siz[u], siz[v]);
}

max_siz[u] = std::max(max_siz[u], sum - siz[u]);
}

void dfs2(int u, int f) {
for (auto e : g[u]) {
int v = e.first,
w = e.second;

if (v == f) continue;

dep[v] = dep[u] + w;
dfs2(v, u);
}
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n;

for (int i = 1; i <= n; i++) {
cin >> c[i];

sum += c[i];
}

for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;

g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}

dfs1(1, 0);

for (int i = 1; i <= n; i++) {
if (!root || max_siz[i] < max_siz[root]) {
root = i;
}
}

dep[0] = -1;
dfs2(root, 0);

for (int i = 1; i <= n; i++) {
ans += static_cast<long long>(c[i]) * dep[i];
}

cout << ans << endl;

return 0;
}