P3884 [JLOI2009] 二叉树问题 题解

· · 题解

思路背景

看到好多人都用一些高级的算法，好像不需要。。。 蔡老师教我们用最简单的算法—— dfs！！！ 其实要写两个深搜，一个求深度和宽度，一个求距离。

代码

#include <bits/stdc++.h>
#define int long long
#define N 105
using namespace std;
int n, u, v, ans1 = 0, ans2 = 0, ans3 = 0, kuan[N];
struct node // 结构体存树
{
    int cld1, cld2;
    int father;
    int deep;
} a[N];
void input() // 输入函数
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        cin >> u >> v;
        if (!a[u].cld1)
            a[u].cld1 = v;
        else
            a[u].cld2 = v;
        a[v].father = u;
    }
    cin >> u >> v;
}
void output() // 输出函数
{
    cout << ans1 << endl << ans2 << endl << ans3;
}
void dfs1(int now, int depth) // 第一个求深度和宽度的dfs
{
    ans1 = max(ans1, depth); // 每次打擂台求最大深度
    a[now].deep = depth;
    kuan[depth]++; // 同一层的结点数++，其实就是求宽度
    ans2 = max(ans2, kuan[depth]); // 打擂台求最大宽度
    if (a[now].cld1) // 如果有左孩子，那就下去
        dfs1(a[now].cld1, depth + 1);
    if (a[now].cld2) // 如果有右孩子，那就下去
        dfs1(a[now].cld2, depth + 1);
}
void dfs2(int now, int last, int dis) // 第二个求距离的dfs
{
    if (now == v) // 如果到了，dis就是答案
    {
        ans3 = dis;
        output();
        exit(0);
    }
    if (a[now].father && a[now].father != last) // 如果有父亲，并且父亲不是上一个访问到的
        dfs2(a[now].father, now, dis + 2); // 注意！根据题目内容，这边有一个技巧：向上+2，向下+1
    if (a[now].cld1 && a[now].cld1 != last) // 如果有左孩子，并且左孩子不是上一个访问到的
        dfs2(a[now].cld1, now, dis + 1);
    if (a[now].cld2 && a[now].cld2 != last) // 如果有右孩子，并且右孩子不是上一个访问到的
        dfs2(a[now].cld2, now, dis + 1);
}
signed main()
{
    input();
    dfs1(1, 1);
    dfs2(u, 0, 0);
    return 0;
}
// 完结散花！！！