847 . 建設高鐵站

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

frostray

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

50.0% (1/2)

Tags

apcsc apcsc-exam4

Description

現充國由 $N$ 個島嶼組成，其中有 $N-1$ 條連接兩個島嶼的雙向橋梁，且任兩個島嶼可以經過若干個橋梁互相抵達。

為了節省通勤時間，現充國的總統 arctan 做了以下決策：

對於兩個島嶼 $A, B$，如果 $A$ 到 $B$ 的路徑需要經過 $K$ 個橋樑，且不存在另外兩個島嶼 $C, D$ ，使得 $C$ 到 $D$ 的路徑需要經過至少 $K+1$ 個橋樑，則在 $A$ 到 $B$ 經過的每個島嶼都建設一個高鐵站，並開通一條往返 $A$ 與 $B$ 的高鐵路線。

請身為現充國總理的你，幫 arctan 總統檢查哪些島嶼需要建設高鐵站。

Input Format

輸入包含多筆測資，第一行輸入包含一個正整數 $T (1 \le T \le 10^ 5)$，代表測資數量。

每筆測資中，

第一行為一個正整數 $N (2 \le N \le 5 \times 10^ 5)$ 代表現充國的島嶼數量，每個島嶼以 $1\sim N$ 的編號代表。

接著的 $N-1$ 行，每行有兩個以一個空白隔開的整數 $u$ 與 $v$ ($1 \le u, v \le N$)，代表編號為 $u$ 跟 $v$ 島嶼之間有橋梁連接。保證任兩個島嶼可以經由若干個橋梁互相抵達。

其中每筆測資中 $N$ 的總和至多為 $10^ 5$。

Output Format

每筆測資輸出一行，其中包含 $N$ 數字，如果第 $i$ 個島嶼需要建設高鐵站則在第 $i$ 個數字輸出 $1$，否則在第 $i$ 個數字輸出 $0$。

Sample Input 1

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

Sample Output 1

1 1 1
1 1 1 1
1 1 1 1 1 0

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~15 每筆測資 $N$ 的總和至多為 $100$ 10
3 0~40 每筆測資 $N$ 的總和至多為 $3000$ 30
4 0~80 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 3 4
1 1000 524288 65536 2 3 4
2 1000 524288 65536 2 3 4
3 1000 524288 65536 2 3 4
4 1000 524288 65536 2 3 4
5 1000 524288 65536 2 3 4
6 1000 524288 65536 2 3 4
7 1000 524288 65536 2 3 4
8 1000 524288 65536 2 3 4
9 1000 524288 65536 2 3 4
10 1000 524288 65536 2 3 4
11 1000 524288 65536 2 3 4
12 1000 524288 65536 2 3 4
13 1000 524288 65536 2 3 4
14 1000 524288 65536 2 3 4
15 1000 524288 65536 2 3 4
16 1000 524288 65536 3 4
17 1000 524288 65536 3 4
18 1000 524288 65536 3 4
19 1000 524288 65536 3 4
20 1000 524288 65536 3 4
21 1000 524288 65536 3 4
22 1000 524288 65536 3 4
23 1000 524288 65536 3 4
24 1000 524288 65536 3 4
25 1000 524288 65536 3 4
26 1000 524288 65536 3 4
27 1000 524288 65536 3 4
28 1000 524288 65536 3 4
29 1000 524288 65536 3 4
30 1000 524288 65536 3 4
31 1000 524288 65536 3 4
32 1000 524288 65536 3 4
33 1000 524288 65536 3 4
34 1000 524288 65536 3 4
35 1000 524288 65536 3 4
36 1000 524288 65536 3 4
37 1000 524288 65536 3 4
38 1000 524288 65536 3 4
39 1000 524288 65536 3 4
40 1000 524288 65536 3 4
41 1000 524288 65536 4
42 1000 524288 65536 4
43 1000 524288 65536 4
44 1000 524288 65536 4
45 1000 524288 65536 4
46 1000 524288 65536 4
47 1000 524288 65536 4
48 1000 524288 65536 4
49 1000 524288 65536 4
50 1000 524288 65536 4
51 1000 524288 65536 4
52 1000 524288 65536 4
53 1000 524288 65536 4
54 1000 524288 65536 4
55 1000 524288 65536 4
56 1000 524288 65536 4
57 1000 524288 65536 4
58 1000 524288 65536 4
59 1000 524288 65536 4
60 1000 524288 65536 4
61 1000 524288 65536 4
62 1000 524288 65536 4
63 1000 524288 65536 4
64 1000 524288 65536 4
65 1000 524288 65536 4
66 1000 524288 65536 4
67 1000 524288 65536 4
68 1000 524288 65536 4
69 1000 524288 65536 4
70 1000 524288 65536 4
71 1000 524288 65536 4
72 1000 524288 65536 4
73 1000 524288 65536 4
74 1000 524288 65536 4
75 1000 524288 65536 4
76 1000 524288 65536 4
77 1000 524288 65536 4
78 1000 524288 65536 4
79 1000 524288 65536 4
80 1000 524288 65536 4
Submit
Back to Top