傳說中蚯蚓國非常特別,
對於任意兩個都市而言, 必定有一條且僅有一條路徑可以連通.
而在這特別的國家中蚯蚓們都活得非常愉快.
但好景不常, 某天, 蚯蚓國與鄰國發生了戰爭！
情急之下, 國王蚯蚓下令所有蚯蚓必須快速集結成軍.
蚯蚓國的軍隊編制一樣也很特別:
每個都市必定會有且只有一支小隊, 每支小隊會各自屬於某個軍旅.
而且當蚯蚓國的軍隊在集結之時, 一定只會朝首都的方向走.
並且, 若有某個蚯蚓小隊走到城市 x 時, 發現有另外一支同軍旅的小隊也正朝 x 走來,
那麼他們就會停下腳步, 等待另外一支小隊走到 x, 並集結成一支新的小隊.
不過當然, 行軍是會有花費的,
人數 a 的小隊經過 b 條道路, 就會消耗掉 a2 * b 的蚯蚓幣.
由於最近國庫十分吃緊, 所以蚯蚓國王希望你能幫他算算,
到底, 讓所有軍旅都各自集結起來, 至少需要花多少蚯蚓幣?
第一行有一個正整數 t, 代表有 t 組測試資料.
每組測試資料的第一行有兩個正整數 N, R 代表有 N 個程式, R 個軍旅.
下一行有 N 個數字, 第 i 個數字 ri 表示第 i 個城市的小隊屬於第 ri 個軍旅.
接下來有 n-1 行, 每行有 a b 兩個數字, 代表城市 a 與城市 b 有道路連通.
另外, 首都永遠都在編號為 1 的都市, 且每個都市剛開始的小隊, 人數都只有 1.
t <= 100
N, R <= 40000
1 <= ri <= R
1 <= a, b <= N
對每筆測資, 請分別對每支軍旅輸出至少需要花多少蚯蚓幣.
格式如範例測資. (每筆測資後請輸出一空白行)
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
1: 0 2: 2 1: 8 2: 6
Migrated from old NTUJ.
IOI2010國手 李瑞珉出題
| No. | Testdata Range | Score |
|---|