#P18707. Cover
Cover
Cover
给定一棵有 个顶点、 条边的树,每个顶点的度数至多为 。
另外给定 条无向简单路径。第 条路径从顶点 出发,到顶点 结束,权值为 。如果删去一条树边 后,顶点 和 不再连通,就称路径 覆盖边 。
请从给定的路径中选出一个子集 ,使每条树边至多被 中的一条路径覆盖,并最大化
不同的选中路径允许经过同一个顶点,只要它们没有共同覆盖的边。也可以不选任何路径。
输入格式
第一行包含三个整数 ,满足 、、。
接下来 行,每行两个整数 (),表示树上有一条连接 的边。保证给出的图是一棵树,且每个顶点的度数至多为 。
接下来 行,第 行包含三个整数 ,满足 、、,描述第 条路径。
输入仅包含一组数据。路径无向,原题不限制不同路径的端点重复。
输出格式
输出一行一个整数,表示所能获得的最大总权值。
样例输入
5 7 3
1 2
1 3
2 4
2 5
3 2 8
5 4 10
3 1 2
1 2 7
2 1 2
1 2 1
5 2 3
样例输出
19
可以选择路径 、、,权值分别为 。这些路径可以共享顶点,但不共享边。