题目背景

\(\text{POJ}\) \(1655\)改编

题目描述

一颗 \(n\) 个节点的无根树，编号 \(1\) ~ \(n\)，找到一个节点 \(x\)，使其满足：\(x\) 为根时，最大子树的节点数最少。\((1≤n≤10^6)\)

最大子树即结点数最多的子树。

格式

输入格式

第一行一个正整数 \(n\)；

以下 \(n-1\)行，每行两个正整数 \(u,v\)，用空格隔开，表示 \(u,v\) 两个结点有边相连。

输出格式

一个正整数 \(x\)，表示树的重心，如果有多个结点满足条件，请输出编号最小的结点。

样例1

样例输入1

7
2 6
1 2
1 4
4 5
3 7
3 1

样例输出1

1

限制

时间：\(1s\) 空间：\(256M\)

对于 \(100\%\) 的数据：\(1≤n≤10^6\)；

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)
模拟赛\(T3\)

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)
模拟赛\(T1\)