这个题作为普及/提高- 难度并不大

可以先把这道题分解成\(3\)个小问题：

\(1\)：求二叉树的深度

\(2\)：求二叉树的宽度

\(3\)：求给定两个结点间距离

先来解决第一个问题：求深度

这个问题很好解决

每一个子结点的深度都是它父亲节点的深度\(+1\)（一号结点的深度是\(1\)）

这个部分很好理解；接下来上这一部分的代码：

for(int i = 1;i < n;i++){               //注意这里循环是到n - 1，按照题目要求，前n - 1行才是需要的
    cin >> root[i] >> son[i];           //我个人喜欢用cin和cout,而且这个题数据点不大，cin cout 没问题
    depth[son[i]] = depth[root[i]] + 1; //子结点的深度是父亲结点的深度 + 1
    fa[son[i]] = root[i];               //一个结点的父亲结点是它本身
}
    int max_depth = 1;                      //用于记录深度
    for(int i = 1;i <= n;i++){
    max_depth = max(max_depth,depth[i]);//求出深度
    width[depth[i]]++;                  //这里是为下一步做准备，再循环统计一次有点浪费
}

然后来解决第二个问题：求宽度

同样，这个问题很好解决

刚才求过了每一个深度都有几个结点（\(width[depth[i]]++;\)）

所以思路也很明确了

上代码：

int max_width = 1;
for(int i = 1;i <= n;i++){
    max_width = max(max_width,width[i]);
}

接着，就是本题的的重头戏：求给定两个结点间距离

思路一（本思路有误）：

分别求出两个结点与\(1\)号结点的深度差

思路二（正确思路）：

求两个结点的最近公共祖先 \(LCA\)

求 \(LCA\) 的方法应是树上倍增

但是这题数据太小了，所以我就用暴力来求解：

int lca(int x,int y){
        if(x == y){
        return x;                  //两个点如果相同，那么 LCA 就是它本身
    }
    else if(depth[x] == depth[y]){  
        return lca(fa[x],fa[y]);   //如果两个点深度相同，就访问它们的父亲结点
    }
    else if(depth[x] < depth[y]){
         return lca(x,fa[y]);       //如果x的深度小于y的深度，就访问y的父亲结点，直到x y 深度相同
    }
    else{
         return lca(fa[x],y);       //原理大致和上一种情况相同，这里就不多解释了
    }
}

最后，贴上AC代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n;
int fa[101],root[101],son[101];

int depth[101],width[101];
int lca(int x,int y){
    if(x == y){
        return x;
    }
    else if(depth[x] == depth[y]){
        return lca(fa[x],fa[y]);
    }
    else if(depth[x] < depth[y]){
        return lca(x,fa[y]);
    }
    else{
        return lca(fa[x],y);
    }
}

int main(){
    cin >> n;
    depth[1] = 1;
    for(int i = 1;i < n;i++){
        cin >> root[i] >> son[i];
        depth[son[i]] = depth[root[i]] + 1;
        fa[son[i]] = root[i];
    }
    int x,y;
    cin >> x >> y;
    int max_depth = 1;
    for(int i = 1;i <= n;i++){
        max_depth = max(max_depth,depth[i]);
        width[depth[i]]++;
    }
    cout << max_depth << endl;
    int max_width = 1;
    for(int i = 1;i <= n;i++){
        max_width = max(max_width,width[i]);
    }
    cout << max_width << endl;
    int k = lca(x,y);      //求 LCA 的结点序号
    cout << (depth[x] - depth[k]) * 2 + depth[y] - depth[k];      //求距离
    return 0;
}