P4872 树的高度（入门）

解题思路

第一步，理解"高度"的含义。 根结点 1 的深度是 1，树的高度就是所有结点中最大的深度。比如根下面有一个孩子，孩子的深度是 2，那么树的高度至少是 2。

第二步，记录每个结点的父亲。 每行输入 a b 表示 b 是 a 的子结点，所以用 par[b]=a 记录 b 的父亲。根结点 1 没有父亲，par[1] 保持 0。

第三步，从每个结点向上数深度。 对每个结点 i，把深度从 1 开始，然后不停往上跳：u=par[u]，每跳一步深度加 1，直到跳到根（par[u]==0）。数出来的就是结点 i 的深度。

第四步，取最大值。 把所有结点的深度放到一起比较，最大的就是树的高度。

类比一下。 就像爬树数层级：从自己站的树枝一格一格往上爬，爬到树顶爬了几格就是自己的深度。把所有位置都数一遍，爬得最高的那个层数就是整棵树的高度。

举个例子。 样例中结点 4 的父亲是 3，3 的父亲是 1，1 没有父亲，深度是 3；结点 5 也一样是 3；其它结点深度更小，所以答案是 3。

边界情况。 如果 n=1，只有根结点，每个结点深度都是 1，答案输出 1。n 最大 100，向上最多走 100 步，不会超时。

参考代码

// 树的高度：从每个结点向上数到根，取最大深度
#include <iostream>
using namespace std;

int par[105];  // 每个结点的父结点，根为0

int main() {
    int n;
    cin >> n;
    int a, b;
    while (cin >> a >> b) par[b] = a;  // b 是 a 的孩子
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        int dep = 1, u = i;
        while (par[u]) { dep++; u = par[u]; }  // 一直往上走到根
        if (dep > ans) ans = dep;
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

时间复杂度。 每个结点最多沿着父亲链向上走到根，链最坏长 O(n)，共 n 个结点，总时间复杂度最坏 O(n²)。n 最大 100，n² 只有 10000，飞快。

空间复杂度。 只用了一个长度为 n 的 par 数组，空间复杂度是 O(n)。