1646 . 士兵集結問題
TopCoder
Tags
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
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
2: 2
1: 8
2: 6
Hints
Problem Source
原TIOJ1646 / Skyly & Shik Contest II (Problem G)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |