【UR #26】街头庆典 - 题目 - Universal Online Judge

在藏蓝铁路的碧水湖大桥落成之际，一群铁路工程蚤聚在一起，庆祝这一伟大的建筑工程。

众多跳蚤走上街头参加庆典，庆祝这一时刻的到来。

为了避免踩踏事故的发生，跳蚤国在一些道路上设置了路障，避免大家聚集在一起。

跳蚤国有 $n$ 个聚落，被 $n-1$ 条道路连接着，使得聚落间两两可达。第 $i$ 条道路连接了第 $u_i,v_i$ 个聚落，在这条道路上设置路障需要 $w_i$ 的代价。每条道路都有相同的长度 $D$ 。

活动中，还需要消耗一定的安保力量。布置安保力量的代价为：聚落和未设置路障的道路所形成的所有连通块的直径长度之和。其中，连通块的直径被定义为连通块中两两聚落间的最短路径的长度的最大值。

举办活动的总代价则为设置路障的代价与布置安保力量的代价之和。

现在，作为杰出的数学家伏特，你需要回答最小总代价。

给定一棵 $n$ 个点的无根树，树上每条边都有相同的长度 $D$。

你可以割掉树上的若干条边，割掉第 $i$ 条边要付出 $w_i$ 的代价。

把一些边割掉后，树变成了若干个连通块。你想使得每个连通块的直径长度之和加上割边付出的代价之和最小，输出这个最小值。

第一行两个正整数 $n$ 和 $D$，表示聚落数和每条道路的长度。

接下来 $n-1$ 行，每行三个正整数 $u_i,v_i,w_i$，表示第 $i$ 条道路连接了第$u_i,v_i$个聚落，在这条道路上设置路障需要 $w_i$ 的代价。

输出一行一个正整数，表示求得的答案。

见下发文件。

对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^5$，$1 \leq D,w_i \leq 10^9$。

子任务编号	$n \leq$	特殊性质	分值
$1$	$20$	无	$5$
$2$	$50$		$5$
$3$	$300$		$10$
$4$	$5000$		$20$
$5$	$2 \times 10^5$	$D=10^9$，$w_i=D-1$	$10$
$6$	$2 \times 10^5$	$w_i$ 在 $[1,D]$ 中均匀随机生成	$15$
$7$	$2 \times 10^5$	无	$35$

时间限制：$3\texttt{s}$

空间限制：$1024\texttt{MB}$

Universal Online Judge