2284 . 方塊王與 Meme X

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

26.7% (4/15)

Submission's AC Ratio

23.9% (11/46)

Tags

CKcon 2022-CKcon

Description

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

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

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

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

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

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

Input Format

第一行會有一個整數 $n$，$1 \leq n \leq 10 ^ 6$
第二行會有 $n$ 個整數 $a_i$， $0 \leq a_i \leq n-1, a_i \neq a_j \ \forall \ i \neq j$
接下來的 $n-1$ 行，每行會有兩個正整數 $u$, $v$，$1 \leq u,v \leq n$, $u \neq v$
代表 $u$ 跟 $v$ 之間有邊
保證輸入是一棵樹

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 $n \leq 500$ 10
3 2~26 $n \leq 5000$ 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
Submit
Back to Top