1646 . 士兵集結問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 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 的小隊經過一條道路，就會當場消耗掉 a2 的蚯蚓幣。

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

Input Format

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

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

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

接下來有 N−1 行，每行有 Xj,Yj 兩個數字（以空白字元分開），代表城市 Xj 與城市 Yj 有道路連通。

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

對於輸入檔，T≤100；對於每一筆測試資料，保證 1≤N,R≤200000，1≤ri≤R，1≤Xj,Yj≤N,∀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
Submit
Back to Top