0 Judge
Code: 0
HH is the world's leading competitive programming country. It consists of $n$ cities labeled from $1$ to $n$, and the cities are connected by roads. Under the planning of the shrewd king of HH, there is exactly one path between any two different cities. In other words, the cities of HH made up a clever tree structure.
HH launched a series of contests to arrange the budget of "Forward-looking Infrastructure Development Program". It has $m$ rounds, and the $i$-th round will determine the distribution of the $i$-th budget. The distribution is based on the result of a double round-robin tournament among $k_i$ cities associated with $i$-th budget. More specifically, considering any two different participating cities $A$ and $B$. There will be a game that $A$ send a team to the city $B$, as well as a game that $B$ send a team to the city $A$. So there will be $k_i \times (k_i - 1)$ games in a round totally.
In order to be able to detail the travel expenses, HH country would like to ask you to calculate the total travelling distance between participating cities of each round. The distance of one game is defined as the number of roads on the only path from the away city to the home city.
The first line contains an integer $T$, denoting the number of test cases. The first line of each test case contains two integers $n$ and $m$, denoting the number of cities and rounds. Each of the next $n - 1$ lines contains two integers $u$ and $v$, denoting a road between the city $u$ and the city $v$. Each of the next $m$ lines contains an integer $k_i$ at the beginning, denoting the number of associated cities in $i$-th round; and followed by $k_i$ integers $c_{i, j}$ in the same line denote the labeles of the these cities.
You may assume:
For each round of the contest, please output an integer, denoting the total travelling distance of that round.
2
2 2
1 2
2 1 2
2 2 1
5 3
1 2
2 3
2 4
1 5
2 3 5
3 3 4 5
5 1 2 3 4 5
2
2
6
16
36
HH 國是世界知名的競技程式設計比賽強國。其國土由 $n$ 座編號 $1$ 到 $n$ 的城市組成,城市之間以道路連接。在精明的 HH 國王規劃之下,任兩座城市之間恰有一條經過若干道路的路徑可以往返。換言之,HH 國的城市組成了一個巧妙的樹型結構。
為了分配各城市在前瞻基礎建設計畫中的預算,HH 國展開了一系列的比賽。比賽共有 $m$ 輪,第 $i$ 輪比賽會決定第 $i$ 項預算的分配,而分配方式則基於與此項預算相關的 $k_i$ 個城市之間雙循環賽的結果。具體而言,任兩個相異的參賽城市 $A, B$ 之間,會有一場由 $A$ 派代表隊去城市 $B$ 進行的比賽,以及一場由 $B$ 派代表隊去城市 $A$ 進行的比賽。整輪共會進行 $k_i \times (k_i - 1)$ 場。
為了能夠詳實的編列交通費,HH 國想請你幫忙算出每輪比賽中,參賽城市間的總移動距離。而其中一場比賽的移動距離則定義為客場城市到主場城市之唯一路徑上的道路數量。
第一行有一個整數 $T$,代表有多少筆測試資料。每筆測試資料的第一行有兩個整數 $n, m$,分別代表 HH 國的城市數以及有幾輪比賽。接下來 $n - 1$ 每行有兩個整數 $u, v$,代表有一條道路連接城市 $u$ 及城市 $v$。接下來 $m$ 行,每行開頭有一個整數 $k_i$,代表有幾座城市參與該輪比賽;同一行中接下來 $k_i$ 個整數 $c_{i, j}$ 則代表這 $k_i$ 座城市的編號。
可假設:
對於每一輪比賽,請輸出一個整數,代表該輪比賽中,參賽城市間的總移動距離。