【UR #5】怎样更有力气 - 题目

大力水手问禅师：“大师，很多事情都需要用很大力气才能完成，而我在吃了菠菜之后力气很大，于是就导致我现在非常依赖菠菜。我很讨厌我的现状，有没有办法少吃点菠菜甚至不吃菠菜却仍很有力气？”

禅师浅笑，答：“方法很简单，不过若想我教你，你需先下山徒手修路。”

山下是 $n$ 座村庄从 $1$ 到 $n$ 编号，之间没有路相连。禅师给了大力水手一张草图，这张草图里 $n$ 座村庄被 $n - 1$ 条双向道路连接，任意一个村庄都可以通过双向道路到达其它所有村庄。

现在大力水手要根据禅师的意思在村庄间修路。禅师规定大力水手需要在 $m$ 天内完成任务，其中大力水手的修路方式如下：

第 $i$ 天，禅师指定了两个村庄 $v_{i}$ 和 $u_{i}$ ，在草图上 $v_{i}$ 号村庄到 $u_{i}$ 号村庄的最短路径上的所有村庄（包括 $v_{i}$ 和 $u_{i}$ ）中，大力水手需要选出若干对村庄（一个村庄可以被重复选多次，当然大力水手在这天也可以一对村庄都不选），然后在选出的每一对村庄间修建双向道路。
在实地考察中大力水手发现，有 $p$ 个限制关系 $(t_{i}, a_{i}, b_{i})$ ，表示在第 $t_{i}$ 天无法在 $a_{i}$ 号村庄到 $b_{i}$ 号村庄间修路（路是双向的，所以自然也无法在 $b_{i}$ 号村庄到 $a_{i}$ 号村庄间修路）。
每一天都有个修理所需力气值 $w_{i}$ ，表示在第 $i$ 天每修建一条道路都要耗费 $w_{i}$ 点力气值。

大力水手开始蛮力干了起来，一罐又一罐地吞食菠菜，结果经常修建一些无用的道路，每天都累得筋疲力尽。

作为一个旁观者，请你帮大力水手求出要想让 $m$ 天后任意一对村庄之间都可以互相到达，所需要的总力气值最少是多少。注意最后修出来的道路不必和草图一致。

输入格式

第一行三个非负整数 $n, m, p$ 。保证 $n \geq 1$ 。

接下来一行 $n - 1$ 个整数，其中第 $i$ 个整数 $f_{i + 1}$ （ $1 \leq f_{i + 1} \leq i$ ）表示草图中 $i + 1$ 号村庄与 $f_{i + 1}$ 号村庄间有一条双向道路。

接下来 $m$ 行，第 $i$ 行包含三个整数 $v_{i}, u_{i}, w_{i}$ （ $1 \leq v_{i}, u_{i} \leq n, v_{i} \neq u_{i}, 1 \leq w_{i} \leq 10^{9}$ ）表示第 $i$ 天禅师指定了 $v_{i}$ 号村庄和 $u_{i}$ 号村庄，大力水手修一条路耗费 $w_{i}$ 点力气值。

接下来 $p$ 行，每行包含三个整数 $t_{i}, a_{i}, b_{i}$ 表示一个限制关系。保证 $1 \leq t_{i} \leq m$ ， $1 \leq a_{i}, b_{i} \leq n$ ， $a_{i} \neq b_{i}$ ，且草图上 $a_{i}$ 号村庄和 $b_{i}$ 号村庄都在 $v_{t_{i}}$ 号村庄到 $u_{t_{i}}$ 号村庄的最短路径上。另外，保证输入中不会出现重复的限制关系，即不会有两个限制关系 $i, j$ 满足 $t_{i} = t_{j}, a_{i} = a_{j}, b_{i} = b_{j}$ 或 $t_{i} = t_{j}, a_{i} = b_{j}, b_{i} = a_{j}$ 。

输出格式

输出一行一个整数，表示所需要的最小总力气值。保证至少存在一种修路的方法使得任意一对村庄之间都可以互相到达。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

output

explanation

第一天大力水手本来可以在 $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$ 间修路，但是由于第一天不能在 $(3, 2), (3, 1)$ 和 $(3, 4)$ 间修路，所以可能的选择只有 $(1, 2), (1, 4), (2, 4)$ 。对于第二天，大力水手可能的选择有 $(3, 4), (3, 5), (4, 5)$ 。

一种可能的最优方案是，第一天大力水手在 $(1, 2), (1, 4)$ 间修路，第二天在 $(3, 4), (4, 5)$ 间修路，总共耗费 $1 + 1 + 2 + 2 = 6$ 点力气值。

样例二

见样例数据下载。这个样例中 $f_{i + 1} = i$ 。

样例三

见样例数据下载。

限制与约定

测试点编号	$n$	$m$	$p$	其他
1	$n \leq 100$	$m \leq 100$	$p \leq 100$	无
2	$n \leq 300000$	$m \leq 300000$	$p = 0$	无
3
4
5	$n \leq 300000$	$m \leq 300000$	$p \leq 300000$	保证对于 $1 < i \leq n$ ， $f_{i + 1} = i$
6	$n \leq 300000$	$m \leq 300000$	$p \leq 300000$	保证对于 $1 < i \leq n$ ， $f_{i + 1} = i$
7	$n \leq 300000$	$m \leq 300000$	$p \leq 300000$	无
8
9
10

时间限制： $1 s$

空间限制： $256 MB$

后记

由于你的帮助，大力水手顺利修完了道路而且使用的力气值是原定计划的 0.01%。

大力水手对禅师说：“我明白了！我以前都是在使用蛮力，从今往后我要多思索，多使用巧力解决问题。”

禅师摆摆手，嘿嘿一笑：“对不起，我只是想请你帮忙修路而已。”

大力水手吃了一罐菠菜，把禅师打死了。

下载

样例数据下载

Universal Online Judge

UOJ

#61. 【UR #5】怎样更有力气