CSP-S 提高级 · CSP 2026 提高级第一轮 第 18 题

【阅读程序3】

说明：输入第一行为结点个数 n，第二行为 n - 1 个整数，依次表示结点 2—n 的父结点编号，满足 2 ≤ n ≤ 100000 且 1 ≤ fa[i] < i，根结点为 1。

#include <iostream>
using namespace std;
int n, fa[100007], f[100007], ans;
int main() {
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];
    }
    for (int i = n; i >= 2; --i) {
        if (f[fa[i]] + f[i] + 1 > ans) {
            ans = f[fa[i]] + f[i] + 1;
        }
        if (f[i] + 1 > f[fa[i]]) {
            f[fa[i]] = f[i] + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

这是"树形 DP 求直径"：f[i] 表示以 i 为根往下走的最长路（边数），因为 fa[i] < i，逆序处理就能保证先算完所有孩子。第一句 if 用"父结点已有的最长路 + 本孩子的最长路 + 1"拼出经过 fa[i] 的最长路径，两棵不同的子树拼起来就是直径。

把 ans 误认为"根到最深叶子的距离"（那只是 f[1]，第 29 题正是考这个区别）；也容易忽略逆序枚举的意义（fa[i] < i 保证了拓扑序）；第 30 题交换两句 if 后 f[fa[i]] 可能已被本孩子更新，导致同一条路径被算两次。

程序分析

int n, fa[100007], f[100007], ans;
int main() {
    cin >> n;
    for (int i = 2; i <= n; ++i) cin >> fa[i];   // 结点 2~n 的父结点，保证 fa[i] < i
    for (int i = n; i >= 2; --i) {               // 逆序：孩子先于父亲被处理
        if (f[fa[i]] + f[i] + 1 > ans)           // 第 10～12 行
            ans = f[fa[i]] + f[i] + 1;
        if (f[i] + 1 > f[fa[i]])                 // 第 13～15 行
            f[fa[i]] = f[i] + 1;
    }
    cout << ans << endl;
}

算法主线：两遍用的都是"子树高度"

• f[i] 的语义：以 i 为根的子树中，从 i 往下走到某个后代能经过的最多边数（即子树高度）。
• 处理顺序：因为题目保证 fa[i] < i，从 i = n 递减到 2，能保证处理 i 时它的所有孩子都已处理完，f[i] 已经是最终值（相当于按"深度优先的逆拓扑序"做树形 DP）。
• 第 13～15 行：用当前孩子 i 的高度 f[i] 去更新父结点的"最大孩子高度" f[fa[i]] —— f[fa[i]] = max(f[fa[i]], f[i] + 1)。
• 第 10～12 行：在更新之前先算一次 f[fa[i]] + f[i] + 1。由于此时 f[fa[i]] 存的是父结点先前已处理过的其他孩子带来的最长下行路，这条式子正是"经过 fa[i] 且两端落在两棵不同子树里的最长路径长度"，它对所有 i 取最大就是树的直径（以边数计）。

注意 f 数组初值为 0，所以当父结点还没有其他孩子时 f[fa[i]] = 0，此时式子退化为"从 fa[i] 往下走到 i 子树深处"的长度，也是合法的候选。

第 28 题（判断）

n = 5，fa[2..5] = {1, 2, 3, 4}，即一条链 1—2—3—4—5。

逆序处理：

输出 4 ✓（链上最远两点 1 与 5 之间正好 4 条边。） 答案：A（正确） ✓

第 29 题（判断）

f[1] 是"根到最深叶子的边数"，ans 是"任意两点间最远的边数（直径）"，两者一般不相等。 反例（就是第 32 题的数据）：n = 7、fa = {1,1,2,2,3,3} 时，树的形状是 1 下面挂 2、3，2 下面挂 4、5，3 下面挂 6、7。此时 f[1] = 2（从 1 到 4/5/6/7 都是 2 条边），而 ans = 4（4—2—1—3—6 共 4 条边）。2 ≠ 4。 答案：B（错误） ✓

第 30 题（判断）

把第 10～12 行与第 13～15 行交换顺序后，f[fa[i]] 会先被本孩子更新，紧接着又用它去算 f[fa[i]] + f[i] + 1 —— 同一个孩子的 f[i] 被算了两次（相当于"从父结点出发，沿同一条边下去又折回来"），结果被系统性放大。 以第 28 题的链为例：交换后 ans 会算到 8（正确值是 4），输出显然被改变。 答案：B（错误） ✓

第 31 题（单选）

由算法主线可知，ans 记录的是"经过某个结点、两端属于两棵不同子树的最长路径"的最大值，即树中距离最远的两个结点之间路径所经过的边数（直径）。 答案：A ✓ （B 是 f[1] 的含义；C、D 与该 DP 完全无关。）

第 32 题（单选）

n = 7，fa[2..7] = {1, 1, 2, 2, 3, 3}：结点 2、3 的父亲是 1；4、5 的父亲是 2；6、7 的父亲是 3。

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

最远点对是"4 或 5"到"6 或 7"，路径如 4—2—1—3—6，共 4 条边。 答案：C（4） ✓ （A 2 是 f[1]；B 3、D 5 都不是任何合法路径长度。）

第 33 题（单选）

要求 n = 10 时输出 9，即树的直径恰为 9 条边。10 个结点的树直径最大就是 9，达到 9 意味着最长路径穿过了全部 10 个结点——这棵树必须是一条链（路径）。

用"逐个插入"来数链的种数：由于每个结点的编号都比父亲大（fa[i] < i），可以按编号 1, 2, 3, …, 10 的顺序把结点插进树里。当前结构要保持"链"的形状，新结点就只能接到当前链的两个端点之一：

合计 1 × 2⁸ = 256 种。

答案：C（256） ✓ （A 0、B 9 远小于实际数量；D 512 = 2⁹ 把结点 2 也算成了 2 种选择。）

交叉验证：程序化枚举全部 1×2×3×…×9 = 362880 种合法输入（满足 fa[i] < i），输出恰为 9 的正好是 256 种，与上面的推导一致。 直观例子：fa = {1, 1, 2, 3, 4, 5, 6, 7, 8}（i = 2…10）对应的链是 10—8—6—4—2—1—3—5—7—9，也恰好 9 条边。

本题小结

套路提示：树形 DP 求直径的模板是"先合并（算答案），再更新（传递高度）"——顺序不能反，这也是第 30 题的考点。同时记住"fa[i] < i"这类编号约束意味着编号本身就是一种拓扑序，逆序枚举即可自底向上。