洛谷P3884:二叉树问题

人生第一篇题解，，

先看原题：二叉树问题

题目描述

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

深度：4 宽度：4（同一层最多结点个数）

结点间距离： ⑧→⑥为8 (3×2+2=8)

⑥→⑦为3 （1×2+1=3）

注：结点间距离的定义：由结点向根方向（上行方向）时的边数×2，

与由根向叶结点方向（下行方向）时的边数之和。

输入输出格式

输入格式：

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

输出格式：

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

那么怎么做呢？

这就是一个裸的LCA

分析一下，很明显的求公共祖先，我们可以用LCA；对于第一个子问题，就是找树上最深的点，一遍dfs即可实现，对于第二个子问题，就是看看相同深度的点数目的最大值是多少，对于对三个子问题，就是通过LCA求两点间的树上距离。

下面上代码：

欸，别激动，我怎么会直接把代码给你cv，，