CF708C.Centroids

Tree is a connected acyclic graph. Suppose you are given a tree consisting of n vertices. The vertex of this tree is called centroid if the size of each connected component that appears if this vertex is removed from the tree doesn't exceed .

You are given a tree of size n and can perform no more than one edge replacement. Edge replacement is the operation of removing one edge from the tree (without deleting incident vertices) and inserting one new edge (without adding new vertices) in such a way that the graph remains a tree. For each vertex you have to determine if it's possible to make it centroid by performing no more than one edge replacement.

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

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

The first line of the input contains an integer n (2 ≤ n ≤ 400 000) — the number of vertices in the tree. Each of the next n - 1 lines contains a pair of vertex indices u__i and v__i (1 ≤ u__i, v__i ≤ n) — endpoints of the corresponding edge.

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

Print n integers. The i-th of them should be equal to 1 if the i-th vertex can be made centroid by replacing no more than one edge, and should be equal to 0 otherwise.

输出 $n$ 个整数。其中第 $i$ 个整数应为 1，当且仅当通过至多替换一条边，可使第 $i$ 个顶点成为树的重心；否则应为 0。

In the first sample each vertex can be made a centroid. For example, in order to turn vertex 1 to centroid one have to replace the edge (2, 3) with the edge (1, 3).

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