luogu#P3884. [JLOI2009] 二叉树问题

    ID: 7912 远端评测题 1000ms 128MiB 尝试: 8 已通过: 3 难度: 3 上传者: 标签>搜索最近公共祖先LCA树上距离树链剖分树剖深度优先搜索DFS各省省选2009吉林

[JLOI2009] 二叉树问题

题目描述

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

  • 深度:44
  • 宽度:44
  • 结点 8 和 6 之间的距离:88
  • 结点 7 和 6 之间的距离:33

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

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

输入格式

第一行是一个整数,表示树的结点个数 nn
接下来 n1n - 1 行,每行两个整数 u,vu, v,表示树上存在一条连接 u,vu, v 的边。
最后一行有两个整数 x,yx, y,表示求 x,yx, y 之间的距离。

输出格式

输出三行,每行一个整数,依次表示二叉树的深度、宽度和 x,yx, 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

提示

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