问题描述

​ 给定一棵有 $n$ 个节点的树。树上有一个数。

​ 这个数的所在节点在 $m$ 个节点 $a_1,\ a_2,\ ...,\ a_m$ 中均匀随机。即该数出现在 $a_1,\ a_2,\ ...,\ a_m$ 的概率均为 $\dfrac{1}{m}$。

​ 面条老师 认为这个数非常优美，于是决定花一定时间找到它。

​ 面条老师 一开始位于节点 $1$。对于一条边 $(u,\ v,\ w)$，面条老师 可以花费 $w$ 的时间从 $u$ 走到 $v$ 或从 $v$ 走到 $u$。

​ 由于 面条老师 体重过大，走过一条边两次之后这条边就再也无法通行了。

​ 假设当前时刻位于节点 $x$，有以下两种情况：

• $x$ 是该数所在的节点。则这时 面条老师 会停下。

• $x$ 不是该数所在的节点。则这时 面条老师 可以选择一条 $x$ 的出边走出。

面条老师 找数心切，没有时间制定最优策略。请你计算如果 面条老师 每一步都按照最优策略来走，找到该数的期望时间。

面条老师 不会在走到数所在节点前知道数的位置，但他已经知道数可能出现的所有位置。

多次询问在不同的 $a$ 数组下的答案，但保证每个点在不同的询问的 $a$ 中最多出现一次。

输入格式

​ 第一行，两个正整数 $n$，$Q(Q \leq 2000)$。$Q$ 表示询问个数。

​ 接下来 $n - 1$ 行，每行三个正整数 $u, v, w$。表示点 $u$ 与点 $v$ 间连有一条边，通过时间为$w$。

​ 接下来 $Q$ 行，每行第一个数位 $m$，接下来 $m$ 个正整数 $a_1,\ a_2,\ ...,\ a_m$。

输出格式

​ $Q$ 行，每行一个浮点数表示答案保留 5 位小数的结果。

4 1
1 2 2
1 3 1
1 4 1
4 1 2 3 4

2.50000

样例 2

​ 见目录下 not2.in/ans。该样例满足数据点 6-7 的性质。

样例 3

​ 见目录下 not3.in/ans。该样例满足数据点 12-13 的性质。

样例解释 1

​ 我们选取按顺序走边 $1 - 3$，$1 - 4$，$1 - 2$ 的策略。

​ 如果数在点 $1$，时间为 $0$。

​ 如果数在点 $2$，时间为 $6$。

​ 如果数在点 $3$，时间为 $1$。

​ 如果数在点 $4$，时间为 $3$。

​ 最优的期望时间为 $\dfrac{0+6+1+3}{4}=2.5$。

数据规模与约定

​ 请注意常数因子对得分的影响。

特殊性质：$v = u + 1$。

对于所有数据满足 $1 \leqslant \sum{m},\ a_i \leqslant n$，$1 \leqslant w \leqslant 100$，$Q \leq 2000$，所有 $a_i$ 互不相同。

大样例

大样例下载