P2052 [NOI2011] 道路修建

题目描述

在 W 星球上有 $n$ 个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 $n-1$ 条双向道路。

每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 $2$ 个、$4$ 个国家，如果该道路长度为 $1$，则费用为 $1\times |2-4|=2$。图中圆圈里的数字表示国家的编号。

由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计算出所需要的费用。请你帮助国王们设计一个这样的软件。

输入格式

输入的第一行包含一个整数 $n$，表示 W 星球上的国家的数量，国家从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行描述道路建设情况，其中第 $i$ 行包含三个整数 $a_i$，$b_i$ 和 $c_i$，表示第 $i$ 条双向道路修建在 $a_i$ 与 $b_i$ 两个国家之间，长度为 $c_i$。

输出格式

输出一个整数，表示修建所有道路所需要的总费用。

输入输出样例 #1

输入 #1

6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1

输出 #1

20

说明/提示

对于 $100\%$ 的数据，$1\le a_i,b_i\le n$，$0\le c_i\le 10^6$，$2\le n\le 10^6$。

测试点编号	$n=$
$1$	$2$
$2$	$10$
$3$	$100$
$4$	$200$
$5$	$500$
$6$	$600$
$7$	$800$
$8$	$1000$
$9$	$10^4$
$10$	$2\times 10^4$
$11$	$5\times 10^4$
$12$	$6\times 10^4$
$13$	$8\times 10^4$
$14$	$10^5$
$15$	$6\times 10^5$
$16$	$7\times 10^5$
$17$	$8\times 10^5$
$18$	$9\times 10^5$
$19,20$	$10^6$

solution

任以一个节点为根节点，dfs 统计每一个子树 u 的 size 对于每条边 e 的长度为 w, 则该边的费用为 w * abs(n - 2 * size), 对所有边费用求和即可

代码

#include<iostream>
#include<algorithm>
#include "cstring"
#include "vector"using namespace std;/** P2052 [NOI2011] 道路修建* 题目大意: 一个有权无向连通图，要得到一颗树，使得费用最小，费用为树的边费用之和，边的费用为边的长度乘以边两端的节点数量之差。** 思路:*      任以一个节点为根节点，dfs 统计每一个子树 u 的 size 对于每条边 e 的长度为 l*      则该边的费用为 l * abs(n - 2 * size), 求和即可**/typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 5;int n;
ll ans;
vector<pii> e[N];int dfs(int u, int p) {int siz = 1;for (auto [v, w]: e[u]) {if (v == p) continue;int siz_v = dfs(v, u);ans += 1ll * abs(n - 2 * siz_v) * w;siz += siz_v;}return siz;
}int main() {cin >> n;for (int i = 1, x, y, w; i < n; i++) {scanf("%d%d%d", &x, &y, &w);e[x].emplace_back(y, w);e[y].emplace_back(x, w);}dfs(1, 0);cout << ans << endl;return 0;
}

结果