10403: 最小高度树
[Creator : ]
Description
树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,任何一个没有简单环路的连通图都是一棵树。
给你一棵包含 $n\ (1 \leq n \leq 5\times 10^5)$ 个节点的树,标记为 $0$ 到 $n-1$。给定数字 $n$ 和一个有 $n-1$ 条无向边的 edges 列表(每一个边都是一对标签),其中 edges[i]=[$a_i,b_i$] 表示树中节点 $a_i$ 和 $b_i$ 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 $x$ 作为根节点时,设结果树的高度为 $h$。在所有可能的树中,具有最小高度的树(即,min(h))被称为最小高度树。
请你找到所有的最小高度树并按升序顺序返回它们的根节点标签列表。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。
给你一棵包含 $n\ (1 \leq n \leq 5\times 10^5)$ 个节点的树,标记为 $0$ 到 $n-1$。给定数字 $n$ 和一个有 $n-1$ 条无向边的 edges 列表(每一个边都是一对标签),其中 edges[i]=[$a_i,b_i$] 表示树中节点 $a_i$ 和 $b_i$ 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 $x$ 作为根节点时,设结果树的高度为 $h$。在所有可能的树中,具有最小高度的树(即,min(h))被称为最小高度树。
请你找到所有的最小高度树并按升序顺序返回它们的根节点标签列表。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。
Input
第一行一个整数 $n$。
其后 $n-1$ 行,每行两个整数 $a_i,b_i$。
输入保证合法,所有 $a_i\neq b_i$。
其后 $n-1$ 行,每行两个整数 $a_i,b_i$。
输入保证合法,所有 $a_i\neq b_i$。
Output
一行,若干个整数,表示答案。
Sample 1 Input
4
1 0
1 2
1 3
Sample 1 Output
1
如果所示。
1. 以 0 为根节点,树的高度为 2。
2. 以 1 为根节点,树的高度为 1。
3. 以 2 为根节点,树的高度为 2。
4. 以 3 为根节点,树的高度为 2。
Sample 2 Input
6
3 0
3 1
3 2
3 4
5 4
Sample 2 Output
3 4
Sample 3 Input
1
Sample 3 Output
0