← 返回题目列表

Codeforces · 708/C

C. 质心

中文机器翻译题面 查看原题

树是一个连通的非循环图。假设给你一棵由 n 个顶点组成的树。如果从树中删除该顶点后出现的每个连通分量的大小不超过 $$\frac{\pi}{2}$$,则该树的顶点称为质心。

给定一棵大小为 n 的树,并且只能执行一个边替换。边替换是从树中删除一条边(不删除关联顶点)并插入一条新边(不添加新顶点)的操作,使得图仍然是一棵树。对于每个顶点,您必须确定是否可以通过执行不超过一条边替换来使其成为质心。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 400 000) — 树中的顶点数。接下来的 n - 1 行中的每一行都包含一对顶点索引 ui 和 vi (1 ≤ ui, vi ≤ n) - 相应边的端点。

输出

打印 n 个整数。如果第 i 个顶点可以通过替换不超过一条边作为质心,则它们中的第 i 个应等于 1,否则应等于 0。

示例

输入 #1

3
1 2
2 3

输出 #1

1 1 1

输入 #2

5
1 2
1 3
1 4
1 5

输出 #2

1 0 0 0 0

注意

在第一个样本中,每个顶点都可以作为质心。例如,为了将顶点 1 转变为质心,必须将边 (2, 3) 替换为边 (1, 3)。