题目描述

树是一种无环连通图。假设给定一棵包含 $n$ 个顶点的树。若删除树中某个顶点后，所有连通分量的大小均不超过 $2n$ ，则该顶点被称为重心。

给定一棵大小为 $n$ 的树，允许执行最多一次边替换操作。边替换是指：从树中移除一条边（不删除关联顶点），并添加一条新边（不增加新顶点），使得操作后的图仍是一棵树。请针对每个顶点判断：是否可以通过最多一次边替换操作使其成为重心。

输入格式

第一行包含整数 $n$ （ $2≤n≤4\times 10^5$ ）表示树的顶点数。

接下来 $n-1$ 行每行包含两个顶点编号 $u_i$ 和 $v_i$ （ $1≤u_i,\ v_i≤n$ ），表示边的端点。

输出 $n$ 个整数。若第 $i$ 个顶点可通过最多一次边替换成为重心，则第 $i$ 个整数为 $1$ ；否则为 $0$ 。

3
1 2
2 3

1 1 1

1 0 0 0 0

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