CSES2079 寻找树的重心
#CS2079. 寻找树的重心
寻找树的重心
题目背景
翻译自 CSES-2079 题。
题目描述
给定一个包含 n 个节点的树，你的任务是找到一个重心节点。重心是指一个节点，当它作为树的根时，树的每个子树的节点数都不超过 ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋，即每个子树的节点数都不超过树节点总数的一半。
输入格式
第一行包含一个整数 n：树中的节点数量。节点编号为 1,2,…,n1,2,…,n1,2,…,n。
接下来有 n−1n−1n−1 行，每行包含两个整数 a 和 b：表示节点 a 和节点 b 之间有一条边。
输出格式
输出一个整数：一个重心节点。如果有多个重心节点，可以输出任意一个。
样例
5
1 2
2 3
3 4
3 5
3
说明/提示