Finding a Centroid

题目描述

给定一棵包含 n 个节点的树，你的任务是找到一个重心节点，也就是当它被指定为树的根时，每个子树的节点数都不超过 $\lfloor n/2 \rfloor$。

输入格式

第一行输入包含一个整数 n：节点数。节点编号为 1,2,$\ldots$,n。 接下来有 n-1 行描述边。每行包含两个整数 a 和 b：表示节点 a 与 节点 b 之间有一条边。

输出格式

输出一个整数：一个重心节点。如果有多个可能，你可以选择其中任意一个。

5
1 2
2 3
3 4
3 5

3

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES2079|树

来源

CSES2079|树