luogu#P3884. [JLOI2009] 二叉树问题
[JLOI2009] 二叉树问题
题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为:
- 深度:
- 宽度:
- 结点 8 和 6 之间的距离:
- 结点 7 和 6 之间的距离:
其中宽度表示二叉树上同一层最多的结点个数,节点 之间的距离表示从 到 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。
给定一颗以 1 号结点为根的二叉树,请求出其深度、宽度和两个指定节点 之间的距离。
输入格式
第一行是一个整数,表示树的结点个数 。
接下来 行,每行两个整数 ,表示树上存在一条连接 的边。
最后一行有两个整数 ,表示求 之间的距离。
输出格式
输出三行,每行一个整数,依次表示二叉树的深度、宽度和 之间的距离。
10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6
4
4
8
提示
对于全部的测试点,保证 ,且给出的是一棵树。保证 是 的父结点。