#P18707. Cover

    ID: 18043 传统题 5000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-树形 DP状压 DPLCA树上倍增子树转区间差分树状数组

Cover

Cover

给定一棵有 nn 个顶点、n−1n-1 条边的树,每个顶点的度数至多为 kk。

另外给定 mm 条无向简单路径。第 ii 条路径从顶点 aia_i 出发,到顶点 bib_i 结束,权值为 wiw_i。如果删去一条树边 ee 后,顶点 xx 和 yy 不再连通,就称路径 (x,y)(x,y) 覆盖边 ee。

请从给定的路径中选出一个子集 SS,使每条树边至多被 SS 中的一条路径覆盖,并最大化

∑i∈Swi.\sum_{i\in S}w_i.

不同的选中路径允许经过同一个顶点,只要它们没有共同覆盖的边。也可以不选任何路径。

输入格式

第一行包含三个整数 n,m,kn,m,k,满足 2≤n≤1052\le n\le 10^5、0≤m≤5×1050\le m\le 5\times10^5、1≤k≤121\le k\le12。

接下来 n−1n-1 行,每行两个整数 x,yx,y(1≤x,y≤n1\le x,y\le n),表示树上有一条连接 x,yx,y 的边。保证给出的图是一棵树,且每个顶点的度数至多为 kk。

接下来 mm 行,第 ii 行包含三个整数 ai,bi,wia_i,b_i,w_i,满足 1≤ai,bi≤n1\le a_i,b_i\le n、ai≠bia_i\ne b_i、0≤wi≤1090\le w_i\le10^9,描述第 ii 条路径。

输入仅包含一组数据。路径无向,原题不限制不同路径的端点重复。

输出格式

输出一行一个整数,表示所能获得的最大总权值。

样例输入

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

可以选择路径 (5,4)(5,4)、(3,1)(3,1)、(1,2)(1,2),权值分别为 10,2,710,2,7。这些路径可以共享顶点,但不共享边。