题目描述

树 是一种连通的无环图。假设给定一棵由 $n$ 个顶点组成的树。如果移除该顶点后，树中每个连通分量的大小均不超过 $\frac{n}{2}$，则该顶点被称为重心。

给定一棵大小为 $n$ 的树，你可以执行最多一次边的替换操作。边的替换操作指的是从树中移除一条边（不删除相邻顶点）并插入一条新边（不添加新顶点），使得图仍保持为一棵树。对于每个顶点，你需要判断是否可以通过执行最多一次边的替换操作使其成为重心。

输入格式

输入的第一行包含一个整数 $n$（$2 \leq n \leq 400000$）——树中顶点的数量。接下来的 $n-1$ 行中，每行包含两个顶点索引 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示对应边的两个端点。

输出格式

输出 $n$ 个整数。第 $i$ 个整数应为 $1$ 如果可以通过替换不超过一条边使第 $i$ 个顶点成为重心，否则应为 $0$。

输入输出样例 #1

输入 #1

3
1 2
2 3

输出 #1

1 1 1

输入输出样例 #2

输入 #2

5
1 2
1 3
1 4
1 5

输出 #2

1 0 0 0 0

说明/提示

在第一个样例中，每个顶点都可以成为重心。例如，为了将顶点 $1$ 变为重心，需要将边 $(2,3)$ 替换为边 $(1,3)$。

翻译由 DeepSeek V3 完成