A70771. 树的宽高及两点的距离
编程题
基础
知识点
题目描述
给定一棵树的边的关系，结点 1 为该树的根，请问该树的宽度（同一层最多的结点数）、高度（根结点的高度为 1 ），以及树中两个结点 u 和 v 之间的最短距离是多少？
比如：下图所示的树，深度为 5，宽度为 3，结点 7 到结点 9 的最短距离为 5。
输入格式
第 1 行输入一个整数 n（n≤1000）；
接下来 n-1 行，每行有 2 个整数 x 和 y，表示结点 x 和 y 之间有一条边（1≤x,y≤n）。
最后一行有 2 个整数 u 和 v ，表示求 u 和 v 之间最短距离。
输出格式
第 1 行输出该树的高度；
第 2 行输出该树的宽度；
第 3 行输出该树从结点 u 到结点 v 之间最短距离；
输入输出样例
输入 #1
10 2 1 1 3 2 4 5 2 3 6 7 4 8 5 9 8 10 8 7 9
输出 #1
5 3 5
说明/提示
## 思路
「树的宽高及两点的距离」建树后 DFS/BFS 统计深度、子树或求 LCA/直径。
## 步骤
1. 读入边并建树。
2. 从根遍历更新深度、父节点或子树大小。
3. 按题意输出询问结果。
「树的宽高及两点的距离」建树后 DFS/BFS 统计深度、子树或求 LCA/直径。
## 步骤
1. 读入边并建树。
2. 从根遍历更新深度、父节点或子树大小。
3. 按题意输出询问结果。