#P11539. [2024省队模拟]树

[2024省队模拟]树

有一棵 nn 个节点的无根树,边有边权,两个结点 x,yx,y 的距离定义为两点之间唯一简单路径的边权和,记作 dis(x,y)dis(x,y) 。

小 YY 给了你 mm 个结点集合,第 ii 个集合为 ViV_i,同时,定义 SiS_i 为一个结点个数最少的、包含 ViV_i 的连通点集,可证明 SiS_i 是唯一确定的。此外还有 mm 个权值 wiw_i 。

你需要选出若干结点集合,若编号从小到大依次是 p1,p2……,pkp_1,p_2……,p_k,你需要再为每个 i∈[1,k]i\in [1,k],选出 xi∈Spix_i\in S_{p_i} 。

定义一组选取方案的权值为:

$$\sum\limits_{i=1}^{k-1}dis(x_i,x_{i+1})+\sum\limits_{i=1}^kw_{p_i}$$

请求出选取方案的最大权值。

输入格式

第一行两个整数 n,mn,m 。

接下来 n−1n-1 行,每行三个数 (x,y,v)(x,y,v) 代表一条边。

接下来 mm 组,每组第一行两个整数 ∣Vi∣,wi|V_i|,w_i ,第二行 ∣Vi∣|V_i| 个整数代表 ViV_i,注意这并不是 SiS_i 。

输出格式

一个整数表示答案。

样例输入

5 2
1 2 3
1 3 9
2 4 6
1 5 1
3 10
5 4 2
4 6
5 2 3 4

样例输出

34

样例解释

最优方案是选择 S1S_1 里的 44 和 S2S_2 里的 33 。

数据规模

记 W=∑∣Vi∣W=\sum|V_i|

  • 20%20\%,n,m,W≤500n,m,W\leq 500
  • 20%20\%,n,m≤5000n,m\leq 5000
  • 20%20\%,∣Vi∣=1|V_i|=1
  • 20%20\%,n,m,W≤105n,m,W\leq 10^5

$1\leq n\leq 10^5,1\leq m\leq W\leq 10^6,1\leq v\leq 10^4,1\leq w\leq10^9$