高雄方塊王是個天才兒童,他從小就去過各種不同的國家,因為太常出國了,他想要規劃各種不同的玩法,現在他想到了一個玩法叫做 Meme X。
玩法是:把整個國家拆成
經過研究,高雄方塊王發現對於任意一個遊玩序列,他所獲得的 Meme 值會跟他沒玩到景點的好玩程度有關,更精確地來說,對任意一條簡單路徑(路徑的起終點可以相同),這條路徑的 Meme 值就是在所有沒有經過的景點中,最小的好玩度是多少,若經過了所有景點,那 Meme 值是
高雄方塊王不會重複玩過一個景點兩次
為了規劃從哪座城市開始玩,高雄方塊王想要對每座城市找出他的 Meme X 值,一座城市的 Meme X 值定義為把所有經過這座城市的簡單路徑的 Meme 值取
高雄方塊王正在忙著破台 IOI 2023,沒有時間寫這個問題,因此他找到了你,請你幫忙幫他找到每座城市的 Meme X 值。
若你不知道什麼是
例如:
第一行會有一個整數
第二行會有
接下來的
代表
保證輸入是一棵樹
輸出
2022 建中校內複賽題目
2024/1/22 21:48 更新:本題測資有誤,感謝 becaido, pingchungchang 指出
已進行更新及 rejudge
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 2~16 | 10 | |
3 | 2~26 | 15 | |
4 | 27~36 | 每個景點至多跟兩條道路相連 | 35 |
5 | 0~46 | 無其他限制 | 40 |