3448 - 【JLOI2009】 二叉树问题

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为:

(1)深度:4

(2)宽度:4

(3)结点 8 和 6 之间的距离:8

(4)结点 7 和 6 之间的距离:3

其中宽度表示二叉树上同一层最多的结点个数,节点 u,v 之间的距离表示从 u 到 v 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。

给定一颗以 1 号结点为根的二叉树,请求出其深度、宽度和两个指定节点 x,y 之间的距离。

输入

第一行是一个整数,表示树的结点个数 n。

接下来 n−1 行,每行两个整数 u,v,表示树上存在一条连接 u,v 的边。

最后一行有两个整数 x,y,表示求 x,y 之间的距离。

输出

输出三行,每行一个整数,依次表示二叉树的深度、宽度和 x,y 之间的距离。

样例

输入

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

输出

4
4
8
说明

【数据说明】

对于全部的测试点,保证 1≤u,v,x,y≤n≤100,且给出的是一棵树。保证 u 是 v 的父结点。

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 4 枚
难度 提高


上一题 下一题