Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:1024 MB
Statistics

题目描述

John 有一个农场,包含 $n$ 个牧场,$n-1$ 个桥,构成一棵树,其中 John 住在牧场 $1$。每个桥都有一个权值 $w$,表示桥的危险程度,值越大越危险。John 住在 $1$ 号牧场。

每天奶牛都会在这 $n$ 个牧场吃字符串,晚上 John 会把奶牛们牛圈里赶,但是奶牛们只会往 $1$ 号牧场的方向走,也就是不会从离 $1$ 号牧场近的牧场往远的牧场走。John 设计了 $m$ 个建牛圈的方案,第 $i$ 个方案中有 $k_i(k_i \geq 1)$ 个牛圈,建在编号为 $p_{i,1},p_{i,2},\dots,p_{i,k_i}$ 的牧场。为了方便,John 一定会在 $1$ 号牧场建牛圈。设把 $j$ 号牧场的奶牛赶到牛圈走过的最危险的桥的危险程度为 $s_j$,John 想知道 $\sum_{j=1}^n s_j$ 的最小值。如果奶牛本来就在牛圈里,危险程度为 $0$。

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行,每行三个正整数 $x,y,w$,表示有一个连接牧场 $x$ 和牧场 $y$ 的桥,权值为 $w$。

一行一个正整数 $m$。

接下来 $m$ 行,每行第一个数 $k_i$,然后 $k_i$ 个正整数 $p_{i,1},p_{i,2},\dots,p_{i,k_i}$。

输出格式

共 $m$ 行,每行一个正整数,表示询问 $i$ 的答案。

样例 #1

样例输入 #1

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

样例输出 #1

0
1
4
4
5

大样例

link

提示

对于 $100\%$ 的数据,保证 $2 \leq n \leq 10^5,\sum k_i \leq 5 \times 10^5,1 \leq x,y,p_{i,j},w \leq n$

Subtask $n \leq$ $\sum k_i \leq$ 特殊性质 分值
$\text{1}$ $100$ $100$ 10
$\text{2}$ $1000$ $10000$ 20
$\text{3}$ $10^5$ $5 \times 10^5$ 树随机生成 30
$\text{4}$ $10^5$ $5 \times 10^5$ 40