Problem G: Critical Node

## Problem G: Critical Node

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 137  Solved: 49
[Submit][Status][Web Board]

## Description

Given a tree $$T$$ whose nodes are numbered from 1 to $$n$$ and the root of the tree is node 1. Define $$dis(x, y)$$ as the distance between node $$x$$ and node $$y$$ (i.e., the least number of edges in the path from node $$x$$ to node $$y$$).

Then define $$k(w)=\sum \limits_{v \in T} dis(w, v)$$. We call a node $$w$$ on tree $$T$$ the critical node if and only if $$k(w)≤\min \limits_{u\in T}k(u)$$. You are asked to print all the critical nodes of the subtree rooted at node $$i$$ for $$i \in [1,n]$$.

## Input

The first line contains an integer $$n$$ $$(1\le n \le 200\ 000)$$, indicating the number of nodes of the tree $$T$$.

Then $$n-1$$ lines follow. Each line contains two integers $$u,v$$ $$(1\le u,v \le n)$$ describing an edge, indicating the indexes of vertexes that connect an edge.

## Output

Output $$n$$ lines.

On the $$i^{th}$$ line, output all the critical nodes of the subtree rooted at node $$i$$ in ascending order. Multiple integers in one line must be separated by one space.

4
1 2
2 3
2 4

2
2
3
4

[Submit][Status]