33OJ
登录 注册

#P17743. [ICPC 2019 Xuzhou R] Kill the tree

[ICPC 2019 Xuzhou R] Kill the tree

Problem Description

Given a tree with NN vertices (vertices are numbered from 11 to NN), where 1 is the root of the tree. The weight of the edges on the tree is 1.

Define d(u,v)d(u, v) as the distance between vertex uu and vv.

Define c(w)=∑v∈Td(w,v)c(w)=\sum \limits_{v \in T} d(w, v). We call a vertex ww on tree TT the critical point, if c(w)≤min⁡u∈Tc(u)c(w) \le \min \limits_{u \in T} c(u).

Now, for all i∈[1,N]i \in [1, N], you must print the "critical points" of the subtree rooted at vertex ii.

Input Format

The first line of the input contains an integer NN denotes the number of vertices of the tree.

Then, N−1N - 1 lines follow, the ithi^{th} line contains two integers ai,bia_i, b_i, denotes the ithi^{th} edge on the tree.

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤ai,bi≤N1 \le a_i, b_i \le N
  • The input is a tree

Output Format

Output NN lines.

On the ithi^{th} line, output the "critical points" of the subtree rooted at vertex ii in ascending order. Two integers in one line must be separated by one space.

4
1 2
2 3
2 4
2
2
3
4