#P17743. [ICPC 2019 Xuzhou R] Kill the tree
[ICPC 2019 Xuzhou R] Kill the tree
Problem Description
Given a tree with vertices (vertices are numbered from to ), where 1 is the root of the tree. The weight of the edges on the tree is 1.
Define as the distance between vertex and .
Define . We call a vertex on tree the critical point, if .
Now, for all , you must print the "critical points" of the subtree rooted at vertex .
Input Format
The first line of the input contains an integer denotes the number of vertices of the tree.
Then, lines follow, the line contains two integers , denotes the edge on the tree.
- The input is a tree
Output Format
Output lines.
On the line, output the "critical points" of the subtree rooted at vertex 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