日本是個非常受臺大資工系學生喜愛的旅遊聖地,據不可信來源的調查資料顯示:寒假的每一天都至少有一個資工系學生正在日本旅遊。
身為資工系的一員,Nathan 也在寒假期間也跑去日本旅遊。不過,在玩的同時,他也不忘把 IOICamp 的事情放在心上。為了讓 IOICamp 能夠順利進行,他決定去神社進行參拜,請求神明保祐營隊能順利進行。
於是,Nathan 來到了一間特別的神社,這間神社由 $N$ 間拜殿以及 $N - 1$ 條步道組成,每條步道會連接兩間拜殿使得對於任兩間拜殿,參拜者都能透過一些步道從期間一間拜殿走到另一間拜殿。此外,神社 8 點就會關門,神社關門了以後,神明就會離開。在神明離開之前,Nathan 希望他能完成恰好 $K$ 次參拜。一次參拜的規則如下:
在每次參拜的過程中,Nathan 都會在參拜的起點拜殿和終點拜殿購買特殊的紀念物品「御朱印帳」。在完成 $K$ 次參拜後,他會恰好購買 $2K$ 本不同的御朱印帳。假設第 $i$ 間拜殿的御朱印帳能帶來 $a_i$ 單位的信仰值,請你幫助 Nathan 計算,他所購買的 $2K$ 本御朱印帳所帶來的信仰值和最大值為多少。
輸入第一行有兩個正整數 $N, K$,分別代表拜殿的數量與 Nathan 的參拜次數。
輸入第二行含有為 $N$ 個正整數,第 $i$ 個數字 $a_i$ 代表第 $i$ 間拜殿的御朱印帳所帶來的信仰值
接下來 $N - 1$ 行,第 $i$ 行有兩個正整數 $u_i, v_i$,代表有一條步道連接了第 $u_i$ 及 $v_i$ 拜殿。
請輸出一個正整數,代表 Nathan 所購買的 $2K$ 本御朱印帳所帶來的信仰值和最大值為多少。若不存在一種方法讓 Nathan 能完成 $K$ 次參拜,請輸出 "The God Had Left..."(不包含引號)。
8 2 6 10 10 2 11 4 12 6 6 2 6 8 1 5 7 4 6 5 7 1 3 7
43
10 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
73
10 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
The God Had Left...
12 3 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
76
IOICamp 2024 Day3 pC
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~3 | 範例測資 | 0 |
2 | 0~45 | 無額外限制 | 100 |