28 . 參拜明奕神社
TopCoder
Tags
Description
日本是個非常受臺大資工系學生喜愛的旅遊聖地，據不可信來源的調查資料顯示：寒假的每一天都至少有一個資工系學生正在日本旅遊。
身為資工系的一員，Nathan 也在寒假期間也跑去日本旅遊。不過，在玩的同時，他也不忘把 IOICamp 的事情放在心上。為了讓 IOICamp 能夠順利進行，他決定去神社進行參拜，請求神明保祐營隊能順利進行。
於是，Nathan 來到了一間特別的神社，這間神社由 $N$ 間拜殿以及 $N - 1$ 條步道組成，每條步道會連接兩間拜殿使得對於任兩間拜殿，參拜者都能透過一些步道從期間一間拜殿走到另一間拜殿。此外，神社 8 點就會關門，神社關門了以後，神明就會離開。在神明離開之前，Nathan 希望他能完成恰好 $K$ 次參拜。一次參拜的規則如下：
- Nathan 會選擇兩間拜殿作為參拜路徑的起點和終點
- 所選的兩間拜殿需滿足，參拜路徑上所經過的每間拜殿都還沒被走訪過
- 完成參拜後，Nathan 會將這次參拜經過的所有拜殿標記為走訪過
在每次參拜的過程中，Nathan 都會在參拜的起點拜殿和終點拜殿購買特殊的紀念物品「御朱印帳」。在完成 $K$ 次參拜後，他會恰好購買 $2K$ 本不同的御朱印帳。假設第 $i$ 間拜殿的御朱印帳能帶來 $a_i$ 單位的信仰值，請你幫助 Nathan 計算，他所購買的 $2K$ 本御朱印帳所帶來的信仰值和最大值為多少。
Input Format
輸入第一行有兩個正整數 $N, K$，分別代表拜殿的數量與 Nathan 的參拜次數。
輸入第二行含有為 $N$ 個正整數，第 $i$ 個數字 $a_i$ 代表第 $i$ 間拜殿的御朱印帳所帶來的信仰值
接下來 $N - 1$ 行，第 $i$ 行有兩個正整數 $u_i, v_i$，代表有一條步道連接了第 $u_i$ 及 $v_i$ 拜殿。
- $2 \leq 2K \leq N \leq 10^ 5$
- $0 \leq a_i \leq 10^ 9$
- $1 \leq u_i, v_i \leq N$
Output Format
請輸出一個正整數，代表 Nathan 所購買的 $2K$ 本御朱印帳所帶來的信仰值和最大值為多少。若不存在一種方法讓 Nathan 能完成 $K$ 次參拜，請輸出 "The God Had Left..."（不包含引號）。
Sample Input 1
6 10 10 2 11 4 12 6
6 2
6 8
1 5
7 4
6 5
7 1
3 7
Sample Output 1
Sample Input 2
11 11 19 19 9 16 17 18 7 9
4 5
2 8
5 7
1 7
10 1
2 5
2 6
2 9
3 8
Sample Output 2
Sample Input 3
18 9 8 13 17 19 0 18 20 18
3 7
1 4
8 4
3 5
3 6
10 3
3 2
3 4
3 9
Sample Output 3
Sample Input 4
13 0 6 0 11 9 14 12 0 19 7 0
2 7
2 10
4 11
4 5
2 4
12 6
12 1
4 12
9 3
9 8
12 9
Sample Output 4
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資。 | 0 |
| 2 | 0~45 | 無特別限制。 | 100 |