#P1403B. Spring cleaning

    ID: 1361 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>*special problemdata structuresdfs and similargraphstrees*2300

Spring cleaning

Description

Spring cleanings are probably the most boring parts of our lives, except this year, when Flóra and her mother found a dusty old tree graph under the carpet.

This tree has NN nodes (numbered from 11 to NN), connected by N1N-1 edges. The edges gathered too much dust, so Flóra's mom decided to clean them.

Cleaning the edges of an arbitrary tree is done by repeating the following process: She chooses 2 different leaves (a node is a leaf if it is connected to exactly one other node by an edge), and cleans every edge lying on the shortest path between them. If this path has dd edges, then the cost of cleaning this path is dd.

She doesn't want to harm the leaves of the tree, so she chooses every one of them at most once. A tree is cleaned when all of its edges are cleaned. The cost of this is the sum of costs for all cleaned paths.

Flóra thinks the tree they found is too small and simple, so she imagines QQ variations of it. In the ii-th variation, she adds a total of DiD_i extra leaves to the original tree: for each new leaf, she chooses a node from the original tree, and connects that node with the new leaf by an edge. Note that some nodes may stop being leaves during this step.

For all these QQ variations, we are interested in the minimum cost that is required to clean the tree.

The first line contains two space-separated integer, NN and QQ (3N1053 \leq N \leq 10^{5}, 1Q1051 \leq Q \leq 10^{5}) – the number of nodes the tree has and the number of variations.

Each of the next N1N-1 lines contains two space-separated integers uu and vv denoting that nodes uu and vv are connected by an edge (1u,vN1 \leq u, v \leq N).

The next QQ lines describe the variations. The first integer in the iith line is DiD_i (1Di1051 \leq D_i \leq 10^{5}). Then DiD_i space-separated integers follow: if the jjth number is aja_j, it means that Flóra adds a new leaf to node aja_j (1ajN1 \leq a_j \leq N). We may add more than one leaf to the same node. 1QDi105\sum_{1}^{Q} D_i \leq 10^{5} i.e. the sum of DiD_i in all varations is at most 10510^5.

After each variation, Flóra restarts and adds extra leaves to the original tree.

You should print QQ lines. In the ii-th line, print a single integer: the minimum cost required to clean the ii-th variation of the tree. If the tree cannot be cleaned, print 1-1.

Scoring

SubtaskPointsConstraints10samples29Q=1,there is an edge between node1andifor everyi(2iN),Floˊra can’t add extra leaf to node139Q=1,there is an edge between nodeiandi+1for all(1i<N),Floˊra can’t add extra leaf to node1nor nodeN416N20000,Q300519the original tree is a perfect binary tree rooted at node 1(i.e. each internal node has exactly 2 children, and every leafhas the same distance from the root)617Di=1for alli730no additional constraints \begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 9 & Q = 1, \text{there is an edge between node} \: 1 \: \text{and} \: i \: \text{for every} \: i \: (2 \leq i \leq N), \\ & & \text{Flóra can't add extra leaf to node} \: 1 \\ \hline 3 & 9 & Q = 1, \text{there is an edge between node} \: i \: \text{and} \: i+1 \: \text{for all} \: (1 \leq i < N), \\ & & \text{Flóra can't add extra leaf to node} \: 1 \: \text{nor node} \: N \\ \hline 4 & 16 & N \leq 20000, Q \leq 300\\ \hline 5 & 19 & \text{the original tree is a perfect binary tree rooted at node $1$} \\ & & \text{(i.e. each internal node has exactly $2$ children, and every leaf} \\ & & \text{has the same distance from the root)}\\ \hline 6 & 17 & D_i = 1 \: \text{for all} \: i\\ \hline 7 & 30 & \text{no additional constraints}\\ \hline \end{array}

Input

The first line contains two space-separated integer, NN and QQ (3N1053 \leq N \leq 10^{5}, 1Q1051 \leq Q \leq 10^{5}) – the number of nodes the tree has and the number of variations.

Each of the next N1N-1 lines contains two space-separated integers uu and vv denoting that nodes uu and vv are connected by an edge (1u,vN1 \leq u, v \leq N).

The next QQ lines describe the variations. The first integer in the iith line is DiD_i (1Di1051 \leq D_i \leq 10^{5}). Then DiD_i space-separated integers follow: if the jjth number is aja_j, it means that Flóra adds a new leaf to node aja_j (1ajN1 \leq a_j \leq N). We may add more than one leaf to the same node. 1QDi105\sum_{1}^{Q} D_i \leq 10^{5} i.e. the sum of DiD_i in all varations is at most 10510^5.

After each variation, Flóra restarts and adds extra leaves to the original tree.

Output

You should print QQ lines. In the ii-th line, print a single integer: the minimum cost required to clean the ii-th variation of the tree. If the tree cannot be cleaned, print 1-1.

Samples

样例输入 1

7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1

样例输出 1

-1
10
8

Note

The following picture shows the second variation. A possible solution is to clean the path between leaves 161 - 6, A7A - 7 and B3 B - 3.

You can download the above example and an additional (bigger) sample input here: https://gofile.io/d/8QlbsS