TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

20.4% (10/49)

Tags

SSC

Description

傳說中有個蚯蚓國非常特別,對於任意兩個都市而言,必定有一條且僅有一條路徑可以連通。

在這特別的國家中蚯蚓們都活得非常愉快。但好景不常,某天,蚯蚓國與油菜國發生了戰爭!

情急之下,國王蚯蚓下令所有蚯蚓必須快速集結成軍,以便順利擊敗油菜國。

蚯蚓國的軍隊編制一樣也很特別:「每個都市必定會有且僅有一支小隊,每支小隊會各自屬於某個軍旅。」而且當蚯蚓國的軍隊在集結之時,一定只會朝首都的方向走。

並且,若有某個蚯蚓小隊走到城市 $v$ 時,發現有另外一支同軍旅的小隊也正朝 $v$ 走來,那麼他們就會停下腳步,等待另外一支小隊走到 $v$,

並集結成一支新的小隊。直到所有屬於某個軍旅的成員都集結在某一點 $u$ 之後,該軍旅便會停止移動,不繼續往首都的方向移動。


不過當然,行軍的過程中是需要花費資源的,當人數 $a$ 的小隊經過一條道路,就會當場消耗掉 $a ^ 2$ 的蚯蚓幣。

由於最近國庫十分吃緊,所以蚯蚓國王希望你能幫他算算,如果想要讓所有軍旅都各自集結起來,至少需要花多少蚯蚓幣?

Input Format

輸入檔第一行有且僅有一個正整數 $T$,代表以下總共有 $T$ 組測試資料。

每組測試資料的第一行有兩個正整數 $N, R$ 代表有 $N$ 個城市和 $R$ 個軍旅。

第二行有 $N$ 個數字,第 $i$ 個數字 $r_i$ 表示第 $i$ 個城市的小隊屬於第 $r_i$ 個軍旅。

接下來有 $N-1$ 行,每行有 $X_j, Y_j$ 兩個數字(以空白字元分開),代表城市 $X_j$ 與城市 $Y_j$ 有道路連通。

首都永遠都是編號為 $1$ 的都市,且在初始狀況,每個都市的小隊人數都只有 $1$。

對於輸入檔,$T \le 100$;對於每一筆測試資料,保證 $1 \le N, R \le 200000$,$1 \le r_i \le R$,$1 \le X_j, Y_j \le N, \forall i, j$。

Output Format

對於每一筆測試資料,請分別對每支軍旅輸出他們至少需要花多少蚯蚓幣。

格式請參考範例輸出。每筆測資後請輸出一個空白行。

Sample Input 1

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

Sample Output 1

1: 0
2: 2

1: 8
2: 6

Hints

Problem Source

原TIOJ1646 / Skyly & Shik Contest II (Problem G)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 12000 131072 262144 1