A70777. 树的中心
编程题
基础
知识点
题目描述
给定一棵树，树中有 n 个结点（结点编号为 1 \sim n ），请求出该树的中心结点的编号。树的中心指的是，该结点离树中的其他结点，最远距离最近。
比如，按照树的中心的定义，下图中的结点 1 和结点 3 ，就是该树的中心。
输入格式
第 1 行包括一个整数 n（n≤10^5），代表树中结点的数量。
接下来 n-1 行，每行有 2 个整数 x 和 y，代表结点 x 到结点 y 之间有一条边。（不确定结点之间的父子关系）
输出格式
请输出树的中心结点的编号，如果有多个中心结点，请按照从小到大的顺序输出所有中心结点的编号。
输入输出样例
输入 #1
5 2 1 1 3 3 4 3 5
输出 #1
1 3
说明/提示
## 思路
「树的中心」建树后 DFS/BFS 统计深度、子树或求 LCA/直径。
## 步骤
1. 读入边并建树。
2. 从根遍历更新深度、父节点或子树大小。
3. 按题意输出询问结果。
「树的中心」建树后 DFS/BFS 统计深度、子树或求 LCA/直径。
## 步骤
1. 读入边并建树。
2. 从根遍历更新深度、父节点或子树大小。
3. 按题意输出询问结果。