AIM Tech Round 3 (Div. 2) E. Centroids （树形dp）

AIM Tech Round 3 (Div. 2) E. Centroids （树形dp）

E. Centroids

time limit per test

memory limit per test

input

output

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

Input

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 ui and vi (1 ≤ ui, vi ≤ n) — endpoints of the corresponding edge.

Output

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

Examples

input

31 22 3

output

1 1 1

input

51 21 31 41 5

output

1 0 0 0 0

Note

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，否则输出0。

题解：枚举每个节点作为根，那么这个节点的子树中，如果只有一个大于n/2，那么就从这个子树中抽取一个最大的不超过n/2的子树，然后接到当前根，如果这个子树还是大于n/2，或者还有子树大于n/2，那么这两种情况是不可以的。

dfs_down跑一遍，把每个节点u为根的其中一棵子树大小dw跑出来，然后跑出来以u为根的一子树中不超n/2的最大的子树，再max一下大小。

dfs_up跑一遍，把另外一棵子树up也跑出来。然后再枚举每个节点的子树，再与n/2比较一下就可以啦。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。