题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：
深度：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间距离。 输入输出样例 输入 #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
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int maxn = 130; int fa[maxn]; int n; int dep[maxn]; int len[maxn]; int main() { int depth = 0, length = 0; cin >> n; int u, v; dep[1] = 1; for(int i = 1; i < n; i++) { cin >> u >> v; fa[v] = u; dep[v] = dep[u] + 1; len[dep[v]]++; depth = max(depth, dep[v]); length = max(length, len[dep[v]]); } cin >> u >> v; int u_step = 0, v_step = 0; while(u != v) { if(dep[u] == dep[v]) { u = fa[u], v = fa[v]; u_step++, v_step++; } else if(dep[u] > dep[v]) { u = fa[u]; u_step++; } else { v = fa[v]; v_step++; } } cout << depth << endl << length << endl; cout << u_step * 2 + v_step; return 0; }