题目描述

给定一棵有 $n$ 个顶点的带权二叉树，以及 $q$ 次询问。

第 $i$ 次询问给出：

• 一个整数 $k_i$；
• 一个由 $k_i$ 个互不相同顶点组成的集合$$S=\{S_1,S_2,\ldots,S_{k_i}\}.$$

你需要再选择一个恰好包含 $k_i$ 个顶点的集合

$$T=\{T_1,T_2,\ldots,T_{k_i}\}.$$

$T$ 可以与 $S$ 有交集，甚至可以令 $T=S$。

目标是最小化

$$\sum_{a=1}^{k_i}\sum_{b=1}^{k_i}\operatorname{dist}(S_a,T_b),$$

其中 $\operatorname{dist}(u,v)$ 表示树上 $u,v$ 之间最短路径的长度。

输入格式

第一行包含两个整数 $n,q$。

接下来 $n-1$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示顶点 $u_i,v_i$ 之间存在一条权值为 $w_i$ 的边。

接下来 $q$ 行描述询问。每行先给出 $k_i$，再给出 $k_i$ 个互不相同的顶点编号。

输出格式

对每次询问输出一行，表示最小可能值。

数据范围

• $1\le n,q\le2\cdot10^5$；
• $1\le w_i\le10$；
• 所有询问的 $k_i$ 之和不超过 $2\cdot10^5$；
• 输入树可以选择某个根，使每个顶点至多有两个儿子。

子任务

子任务	分值	限制
1	0	样例
2	10	$n,q\le200$，$\sum k_i\le400$
3	15	$n,q\le2000$，$\sum k_i\le4000$
4	20	树是一条链
5	55	无额外限制

样例

输入

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

输出

51
306
128
280
103

样例中的树

第一问中，选择 $T=\{1,8,7\}$ 时总代价为 $51$。