← 返回题单
题单练习 树及树的应用
← 上一题 下一题 →

A70771 | 树的宽高及两点的距离

来源编程题
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一棵树的边的关系，结点 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
C++ 编辑器
输入
输出