[JLOI2009]二叉树问题

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为: 深度:4 宽度:4(同一层最多结点个数) 结点间距离: ⑧→⑥为8 (3×2+2=8) ⑥→⑦为3 (1×2+1=3) 注:结点间距离的定义:由结点向根方向(上行方向)时的边数×2, 与由根向叶结点方向(下行方向)时的边数之和。 ![](https://cdn.luogu.com.cn/upload/pic/6843.png)

输入输出格式

输入格式


输入文件第一行为一个整数n(1≤n≤100),表示二叉树结点个数。接下来的n-1行,表示从结点x到结点y(约定根结点为1),最后一行两个整数u、v,表示求从结点u到结点v的距离。

输出格式


三个数,每个数占一行,依次表示给定二叉树的深度、宽度及结点u到结点v间距离。

输入输出样例

输入样例 #1

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

输出样例 #1

4
4
8