U328173 【模板】树的重心

题目背景

本蒟蒻正在学习树的重心,然而搜不到对应模板题,于是自己出了一道模板题。

题目描述

给定一棵无根树,求这棵树的重心(可能有多个)。 计算以无根树每个点为根节点时的最大子树大小,这个值最小的点称为无根树的重心。

输入格式

第一行一个整数 $n$ 代表树的点数。 接下来 $n - 1$ 行,每行两个整数 $u, v$,代表 $u, v$ 之间有一条无向边。

输出格式

一行多个整数,表示你找到的所有重心的节点编号,升序排列。

说明/提示

### 样例解释 #### 样例1解释 样例1中的树如下图所示: ![样例1图片](https://cdn.luogu.com.cn/upload/image_hosting/c38yh0uq.png) 注意到,选取 $1$ 号节点为重心,其所有的子树中最大的子树节点数为 $3$。没有其他节点的所有的子树中最大的子树节点数小于等于 $3$。 #### 样例2解释 样例2中的树如下图所示: ![样例2图片](https://cdn.luogu.com.cn/upload/image_hosting/cxyfrzwv.png) 注意到,选取 $1, 2$ 号节点为重心,其所有的子树中最大的子树节点数为 $3$。没有其他节点的所有的子树中最大的子树节点数小于等于 $3$。 ### 数据范围及约定 | 测试点编号| 特殊性质 | | :--------: | :---------: | | 1 | A | | 2 | 无 | | 3 | 无 | | 4 | 无 | | 5 | 无 | | 6 | B | | 7 | A & B | - 特殊性质A:$n \le 1000$。 - 特殊性质B:树是一条链。 对于 $100\%$ 的数据,保证 $1 \le n \le 10^6, 1 \le u, v \le n$。保证没有重边或自环。