TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

52.9% (9/17)

Tags

Description

聖瑪格諾利亞共和國是一個規模龐大的國家,由 $N$ 個行政區組成,並且有 $N-1$ 條連接行政區與行政區的道路,讓任意兩個行政區都能互相往來。

由於最近國勢動盪,大總統為了防止鞏固勢力,決定重新劃分領土。他打算封鎖一些行政區,並且將每一個沒有被封鎖的行政區都指派到某個領域的管轄之內,使得任兩個屬於不同領域的行政區之間都沒有直接連接彼此的道路。

大總統命令你來決定要封鎖哪些行政區以及如何劃分各個領域。當然,這份差事沒有這麼簡單,他還給了你一個額外的要求:每一個行政區都有一個神秘的標記 $c_i$,當某一個行政區被選擇要封鎖時,其他與它擁有相同標記且距離為偶數的行政區也必須被選上。距離的定義是兩個行政區之間最少需要經過幾條道路才能到達,與中間的行政區是否被封鎖無關。

為了給出一個能讓大總統滿意的規劃,在滿足要求的方案之中,請找到任意一個包含最多領域的方式。

Input Format

輸入第一行為一個整數 $N$,代表行政區的數量。接下來的 $N-1$ 行,每行包含兩個以空格隔開的整數 $u_i, v_i$,代表有一條雙向的道路連接 $u_i, v_i$ 兩個行政區。最後一行包含 $N$ 個以空格隔開的整數 $c_1, c_2, \ldots, c_N$,$c_i$ 為第 $i$ 個行政區的標記。

  • $1 \le N \le 5 \times 10^ 4$
  • $1 \le u_i, v_i \le N$
  • $1 \le c_i \le 5 \times 10^ 4$

Output Format

請輸出兩行。第一行為一個整數,代表最多能有幾個領域。第二行先輸出一個整數 $K$,代表要被封鎖的行政區數量,再輸出 $K$ 個由小到大的整數,代表要封鎖的行政區,中間皆以空格隔開。

當有多種滿足要求的選擇能讓領域數量最多時,可以輸出任意一組解。

如果你的第一行輸出正確,並且在第二行只輸出一個整數 $-1$,你將獲得一半的分數。

Sample Input 1

9
1 2
2 4
4 8
2 5
5 9
1 3
3 6
3 7
1 2 2 3 3 2 2 1 1

Sample Output 1

5
4 2 3 4 5

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~53 無額外限制 100

Testdata and Limits

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