传送门：P3884 [JLOI2009] 二叉树问题

更佳的阅读体验：洛谷 P3884 题解

本文给出一种不使用 LCA 等较高级算法的解法。

简要题意：给定一棵二叉树，求其深度、宽度，和节点 $x$ 到 $y$ 的距离。其中距离定义为向根节点的边数的两倍加上向叶节点的边数。

我们来分析二叉树的性质。

首先是深度。深度定义为从根节点到最远叶结点的节点数，也就是说从根节点出发，不回头可以走到最远的路径长度。从根节点开始使用一遍 DFS 遍历整棵树即可求出。

然后是宽度。宽度定义为具有最多结点数的层中包含的结点数。此时需要意识到，从根节点出发，到同一层的所有节点的路径长度都相同。也就是说，从根节点出发，路径长度相同的节点位于同一层。

因此，我们可以开一个桶，在遍历的同时记录每一层的节点数。桶中的最大值就是树的宽度。

接下来问题就只剩节点 $x$ 到 $y$ 的距离了。因为距离定义为“向根节点的边数的两倍加上向叶节点的边数”，我们发现在一棵树上直接求解是十分困难的。

我们需要考虑如何转化问题。由距离的定义可以想到，本题中距离的本质是“根节点到叶节点的距离为 $1$，叶节点到根节点的距离为 $2$”。

此时，想到直接对整棵树建图，根节点到叶节点的边权为 $1$，叶节点到根节点的边权为 $2$。注意到 $n \le 100$，我们直接以 $x$ 为起点，再进行一次 DFS 遍历，即可求出到 $y$ 的距离。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
int n, u, v, x, y, depth, cnt[N], width, ans;
basic_string<pair<int, int> > g[N];

void dfs1(int u, int fa, int dep) {
    depth = max(depth, dep), ++cnt[dep];
    for (auto [v, w] : g[u]) {
        if (v == fa) continue;
        dfs1(v, u, dep + w);
    }
}

void dfs2(int u, int fa, int dis) {
    if (u == y) ans = dis;
    for (auto [v, w] : g[u]) {
        if (v == fa) continue;
        dfs2(v, u, dis + w);
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        g[u] += make_pair(v, 1), g[v] += make_pair(u, 2);
    } cin >> x >> y;
    dfs1(1, 0, 1);
    width = *max_element(cnt + 1, cnt + depth + 1);
    dfs2(x, 0, 0);
    cout << depth << '\n' << width << '\n' << ans << '\n';
    return 0;
}