2204: 【基础】树的宽高及两点的距离

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

给定一棵树的边的关系,结点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之间最短距离;

输入样例 复制

10
2 1
1 3
2 4
5 2
3 6
7 4
8 5
9 8
10 8
7 9

输出样例 复制

5
3
5

分类标签