1. 算法核心思路

这道题是一个经典的树上覆盖问题：选取最少的点（建立消防局），使得树上所有点到选中点的距离 $\le 2$。

代码并没有使用贪心算法（虽然贪心也可解），而是使用了状态更加严谨的 DP。它定义了两个状态数组 f 和 g，分别表示“子树已完全覆盖”和“子树未完全覆盖”的情况。

状态定义

设 $u$ 为当前节点：

1. $f[u][i]$：表示以 $u$ 为根的子树 全部被覆盖，且 $u$ 子树内距离 $u$ 最近的消防局距离为 $i$（$0 \le i \le 2$）。

   • $f[u][0]$：$u$ 自己就有消防局。
   • $f[u][1]$：$u$ 的某个子节点有消防局。
   • $f[u][2]$：$u$ 的某个孙子节点有消防局（正好覆盖到 $u$）。

2. $g[u][i]$：表示以 $u$ 为根的子树 有部分节点未被覆盖，且这部分未被覆盖的节点中，距离 $u$ 最远的距离为 $i$（$0 \le i \le 2$）。

   • $g[u][0]$：$u$ 自己没被覆盖。
   • $g[u][1]$：$u$ 被覆盖了，但 $u$ 的某个子节点没被覆盖（需要 $u$ 的父辈来救）。
   • $g[u][2]$：$u$ 和子节点都覆盖了，但 $u$ 的某个孙子节点没被覆盖。

注意：代码中的 i 循环范围是 $0 \sim 4$，但实际有效的逻辑只用到了 $0 \sim 2$。较大的索引仅作为中间计算或边界处理。

2. 状态转移逻辑

在 dfs 过程中，通过合并父节点 $x$ 和子节点 $u$ 的状态来更新 $x$。使用临时数组 ff 和 gg 存储合并后的状态，最后赋回给 f[x] 和 g[x]。

对于父节点 $x$ 的每一个状态 $i$ 和子节点 $u$ 的每一个状态 $j$，分四种情况讨论：

1. $f[x][i]$ + $f[u][j]$ （两者都已覆盖）

   • 合并后子树依然是全覆盖的。
   • 最近的消防局距离变为 $\min(i, j+1)$。因为 $u$ 的消防局距离 $x$ 的距离是 $j+1$。
   • 转移：ff[min(i, j + 1)] = min(..., f[x][i] + f[u][j])

2. $f[x][i]$ + $g[u][j]$ （$x$ 覆盖，$u$ 未全覆盖）

   • $x$ 子树内的消防局距离 $x$ 为 $i$，$u$ 子树内最远未覆盖点距离 $x$ 为 $j+1$。
   • 关键判断：$i + (j+1) \le 2$ ？
     • 是：说明 $x$ 这边的消防局够得着 $u$ 那边未覆盖的点。于是整体变为“全覆盖”状态。距离仍由 $x$ 决定（因为 $u$ 那边没有提供更有用的消防局），即 f 状态，距离 $i$。
     • 否：救不到。整体依然是“未全覆盖”。最远未覆盖点距离 $x$ 为 $j+1$。即 g 状态。

3. $g[x][i]$ + $f[u][j]$ （$x$ 未全覆盖，$u$ 覆盖）

   • 同理，判断 $u$ 的消防局能否覆盖 $x$ 的遗留问题。距离为 $(j+1) + i$。
   • 关键判断：$i + j + 1 \le 2$ ?
     • 是：覆盖成功。整体变为 f 状态，最近消防局距离为 $j+1$。
     • 否：覆盖失败。整体仍为 g 状态，最远未覆盖点距离为 $i$。

4. $g[x][i]$ + $g[u][j]$ （两者都未全覆盖）

   • 肯定救不了，状态依然是 g。
   • 最远未覆盖点距离取最大值：$\max(i, j+1)$。

3. 初始化与答案

• 初始化：对于叶子节点（或刚开始处理的节点）：

  • $f[x][0] = 1$：放一个消防局，代价为 1，距离为 0。
  • $g[x][0] = 0$：不放，代价为 0，自己($x$)未被覆盖，距离为 0。
  • 其余初始化为无穷大（代码中是 $n+1$）。

• 答案：

  • 根节点 $1$ 必须被覆盖。
  • 结果为 $\min(f[1][0], f[1][1], f[1][2])$。

4. 代码详解

#include <bits/stdc++.h>
using namespace std;

// 快速读写模板 IO (省略...)
namespace IO { ... }
using namespace IO;

const int N = 1005;
int n, p[N]; 
int f[N][5], g[N][5]; // DP数组
int ff[5], gg[5];     // 临时数组用于状态合并
vector<int> e[N];     // 邻接表存图

void dfs(int x) {
    // 1. 初始化当前节点 x 的状态
    for (int i = 0; i < 5; i++) {
        f[x][i] = g[x][i] = n + 1; // 初始化为极大值
    }
    f[x][0] = 1; // 在 x 建站：已覆盖，距离0，花费1
    g[x][0] = 0; // 不建站：未覆盖，坏点距离0，花费0

    // 2. 遍历子节点 u
    for (int u : e[x]) {
        dfs(u); // 递归处理子树

        // 初始化临时数组
        for (int i = 0; i < 5; i++)
            ff[i] = gg[i] = n + 1;

        // 3. 状态合并：枚举 x 的状态 i 和 u 的状态 j
        // 这里只枚举到 3 其实就够了，因为题目只关心距离 <= 2
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                // Case 1: f + f (都已覆盖)
                // x 最近站距离 i，u 最近站距离 j (相对于 x 是 j+1)
                // 新的最近距离是 min(i, j+1)
                ff[min(i, j + 1)] = min(ff[min(i, j + 1)], f[x][i] + f[u][j]); 

                // Case 2: f + g (x 覆盖, u 未覆盖)
                // x 站距离 i，u 坏点距离 j (相对于 x 是 j+1)
                // 距离和 i + j + 1 <= 2 说明能覆盖
                if (i + j + 1 <= 2)
                    ff[i] = min(ff[i], f[x][i] + g[u][j]); // 覆盖了，状态变为 f
                else
                    gg[j + 1] = min(gg[j + 1], f[x][i] + g[u][j]); // 没覆盖到，状态仍为 g

                // Case 3: g + f (x 未覆盖, u 覆盖)
                // x 坏点距离 i，u 站距离 j (相对于 x 是 j+1)
                if (i + j + 1 <= 2)
                    ff[j + 1] = min(ff[j + 1], g[x][i] + f[u][j]); // 覆盖了，状态变为 f
                else
                    gg[i] = min(gg[i], g[x][i] + f[u][j]); // 没覆盖到，状态仍为 g

                // Case 4: g + g (都未覆盖)
                // 取最远的坏点距离
                gg[max(i, j + 1)] = min(gg[max(i, j + 1)], g[x][i] + g[u][j]);
            }
        }

        // 将临时数组的值赋回 f[x] 和 g[x]
        for (int i = 0; i < 5; i++)
            f[x][i] = ff[i], g[x][i] = gg[i];
    }
}

signed main() {
    read(n);
    // 建树。题目输入 a_i 表示 i 到 a_i 有边，且 a_i < i。
    // 所以 a_i 是 i 的父节点。为了 dfs，建立父指向子的边。
    for (int i = 2; i <= n; i++)
        read(p[i]), e[p[i]].push_back(i);

    dfs(1);
    
    // 最终答案：根节点必须被覆盖，取 f[1][0...2] 的最小值
    out(min(f[1][0], min(f[1][1], f[1][2])));
    return 0;
}

5. 复杂度分析

• 时间复杂度：$O(N)$。虽然状态转移有双重循环，但循环次数是常数（$3 \times 3$），每个节点只遍历一次。
• 空间复杂度：$O(N)$。用于存储图结构和 DP 数组。

这段代码逻辑清晰，分类讨论全面，能够正确解决该题。