Description

In a war, the battlefield consists of $n$ islands connected by $n-1$ bridges, and there is exactly one simple path between any two islands. Our intelligence has located the enemy headquarters on island $1$. The enemy lacks sufficient energy to sustain combat, and victory is in sight. It is known that there are rich energy reserves on another $k$ islands. To prevent the enemy from obtaining energy, our task is to blow up some bridges so that the enemy cannot reach any energy-rich island from island $1$. Since different bridges have different materials and structures, the cost to destroy each bridge varies. We want to minimize the total cost while achieving the objective.

Intelligence also found that the enemy has a mysterious machine. Even after we cut off all energy, they can use that machine. The machine will not only repair all bridges we blew up, but also randomly redistribute the energy (with the guarantee that no energy will be placed on island $1$). However, the machine can be used only $m$ times, so we only need to complete the task for each use.

Input Format

The first line contains an integer $n$, the number of islands.

The next $n-1$ lines each contain three integers $u, v, w$, indicating that islands $u$ and $v$ are directly connected by a bridge with destruction cost $w$.

The $(n+1)$-th line contains an integer $m$, the number of times the enemy can use the machine.

Then follow $m$ lines. On the $i$-th line, there is an integer $k_i$, meaning that after the $i$-th reset there are $k_i$ energy-rich islands, followed by $k_i$ integers $h_1, h_2, \ldots, h_{k_i}$, which are the indices of the energy-rich islands.

Output Format

Output $m$ lines. For each use of the machine, output the minimum total cost required to prevent the enemy from reaching any energy-rich island from island $1$.

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

12
32
22

Hint

Constraints

• For $10\%$ of the testdata, $n \leq 10$, $m \leq 5$.
• For $20\%$ of the testdata, $n \leq 100$, $m \leq 100$, $1 \leq k_i \leq 10$.
• For $40\%$ of the testdata, $n \leq 1000$, $1 \leq k_i \leq 15$.
• For $100\%$ of the testdata, $2 \leq n \leq 2.5\times 10^5$, $1 \leq m \leq 5\times 10^5$, $\sum k_i \leq 5\times 10^5$, $1 \leq k_i < n$, $h_i \neq 1$, $1 \leq u, v \leq n$, $1 \leq w \leq 10^5$.

Translated by ChatGPT 5