#2568. 「APIO2016」烟花表演

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安全,烟花被安置在远离开关的位置上,通过一些导火索与开关相连。导火索的连接方式形成一棵树,烟花是树叶,如图 1所示。火花从开关出发,沿导火索移动。每当火花抵达一个分叉点时,它会扩散到与之相连的所有导火索,继续燃烧。导火索燃烧的速度是一个固定常数。图 1展示了六枚烟花 {E1,E2,…,E6}\{E_1, E_2, \ldots, E_6 \}{E1,E2,,E6} 的连线布局,以及每根导火索的长度。图中还标注了当在时刻 000 从开关点燃火花时,每一发烟花的爆炸时间。

图 1

图 1

Hyunmin 为烟花表演设计了导火索的连线布局。不幸的是,在他设计的布局中,烟花不一定同时爆炸。我们希望修改一些导火索的长度,让所有烟花在同一时刻爆炸。例如,为了让图 1中的所有烟花在时刻 131313 爆炸,我们可以像图 2中左边那样调整导火索长度。类似地,为了让图 1中的所有烟花在时刻 141414 爆炸,我们可以像图 2中右边那样调整长度。

图 2

图 2

修改导火索长度的代价等于修改前后长度之差的绝对值。例如,将图 1中布局修改为图 2,左边布局的总代价为 666,而将图 1中布局修改为图 2右边布局的总代价为 555

导火索的长度可以被减为 000,同时保持连通性不变。

给定一个导火索的连线布局,你需要编写一个程序,去调整导火索长度,让所有的烟花在同一时刻爆炸,并使得代价最小。

输入格式

所有的输入均为正整数。令 NNN 代表分叉点的数量,MMM 代表烟花的数量。分叉点从 111NNN 编号,编号为 111 的分叉点是开关。烟花从 N+1N+1N+1N+MN+MN+M 编号。

输入格式如下:
NMN\:\:MNM
P2C2P_2\:\:C_2P2C2
P3C3P_3\:\:C_3P3C3
…\ldots
PNCNP_N\:\:C_NPNCN
PN+1CN+1P_{N+1}\:\:C_{N+1}PN+1CN+1
…\ldots
PN+MCN+MP_{N+M}\:\:C_{N+M}PN+MCN+M
其中 PiP_iPi 满足 1≤Pi<i1\le P_i<i1Pi<i,代表和分叉点或烟花 iii 相连的分叉点。CiC_iCi 代表连接它们的导火索长度 (1≤Ci≤109)(1\le C_i\le 10^9)(1Ci109)。除开关外,每个分叉点和多于 111 条导火索相连,而每发烟花恰好与 111 条导火索相连。

输出格式

输出调整导火索长度,让所有烟花同时爆炸,所需要的最小代价。

样例

样例输入

4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3

样例输出

5

数据范围与提示

子任务 1(7 分):N=1,1≤M≤100N=1,1 \le M \le 100N=1,1M100

子任务 2(19 分):1≤N+M≤3001 \le N+M \le 3001N+M300,且开关到任一烟花的距离不超过 300300300

子任务 3(29 分):1≤N+M≤50001 \le N+M \le 50001N+M5000

子任务 4(45 分):1≤N+M≤3×1051 \le N+M \le 3\times 10^51N+M3×105