TopCoder

Caido
Waimai

User's AC Ratio

26.7% (4/15)

Submission's AC Ratio

23.9% (11/46)

Tags

Description

高雄方塊王是個天才兒童,他從小就去過各種不同的國家,因為太常出國了,他想要規劃各種不同的玩法,現在他想到了一個玩法叫做 Meme X。

玩法是:把整個國家拆成 n 座景點,某些景點與景點間有直接道路相連,滿足任兩個景點與景點間有唯一的簡單路徑連通,然後每個景點有一個好玩度,好玩度是一個界在 0n1 的整數,並且滿足每個景點的好玩度皆不相同。

經過研究,高雄方塊王發現對於任意一個遊玩序列,他所獲得的 Meme 值會跟他沒玩到景點的好玩程度有關,更精確地來說,對任意一條簡單路徑(路徑的起終點可以相同),這條路徑的 Meme 值就是在所有沒有經過的景點中,最小的好玩度是多少,若經過了所有景點,那 Meme 值是 n
高雄方塊王不會重複玩過一個景點兩次

為了規劃從哪座城市開始玩,高雄方塊王想要對每座城市找出他的 Meme X 值,一座城市的 Meme X 值定義為把所有經過這座城市的簡單路徑的 Meme 值取 mex

高雄方塊王正在忙著破台 IOI 2023,沒有時間寫這個問題,因此他找到了你,請你幫忙幫他找到每座城市的 Meme X 值。

若你不知道什麼是 mexmex 的定義是最小不存在這個集合裡的非負整數,
例如:mex(1,3,5)=0, mex(0,1,2,4,5,49)=3 等等。

Input Format

第一行會有一個整數 n1n106
第二行會有 n 個整數 ai0ain1,aiaj  ij
接下來的 n1 行,每行會有兩個正整數 u, v1u,vn, uv
代表 uv 之間有邊
保證輸入是一棵樹

Output Format

輸出 n 個數字,第 i 個數字分別代表第 i 個點的 Meme X 值

Sample Input 1

4
0 3 2 1
1 2
3 4
2 3

Sample Output 1

0 2 2 1

Sample Input 2

6
4 0 1 5 3 2
1 2
3 5
5 2
4 6
5 4

Sample Output 2

3 0 1 2 3 2

Hints

Problem Source

2022 建中校內複賽題目

2024/1/22 21:48 更新:本題測資有誤,感謝 becaido, pingchungchang 指出
已進行更新及 rejudge

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~16 n500 10
3 2~26 n5000 15
4 27~36 每個景點至多跟兩條道路相連 35
5 0~46 無其他限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 5
1 3000 262144 65536 1 5
2 3000 262144 65536 2 3 5
3 3000 262144 65536 2 3 5
4 3000 262144 65536 2 3 5
5 3000 262144 65536 2 3 5
6 3000 262144 65536 2 3 5
7 3000 262144 65536 2 3 5
8 3000 262144 65536 2 3 5
9 3000 262144 65536 2 3 5
10 3000 262144 65536 2 3 5
11 3000 262144 65536 2 3 5
12 3000 262144 65536 2 3 5
13 3000 262144 65536 2 3 5
14 3000 262144 65536 2 3 5
15 3000 262144 65536 2 3 5
16 3000 262144 65536 2 3 5
17 3000 262144 65536 3 5
18 3000 262144 65536 3 5
19 3000 262144 65536 3 5
20 3000 262144 65536 3 5
21 3000 262144 65536 3 5
22 3000 262144 65536 3 5
23 3000 262144 65536 3 5
24 3000 262144 65536 3 5
25 3000 262144 65536 3 5
26 3000 262144 65536 3 5
27 3000 262144 65536 4 5
28 3000 262144 65536 4 5
29 3000 262144 65536 4 5
30 3000 262144 65536 4 5
31 3000 262144 65536 4 5
32 3000 262144 65536 4 5
33 3000 262144 65536 4 5
34 3000 262144 65536 4 5
35 3000 262144 65536 4 5
36 3000 262144 65536 4 5
37 3000 262144 65536 5
38 3000 262144 65536 5
39 3000 262144 65536 5
40 3000 262144 65536 5
41 3000 262144 65536 5
42 3000 262144 65536 5
43 3000 262144 65536 5
44 3000 262144 65536 5
45 3000 262144 65536 5
46 3000 262144 65536 5