==$\color{yellow}{只写给自己看防止自己忘了的emmm}$==

主要思路是从叶节点开始向根节点进行转移

一共有五个状态,f[i][0...4]

0 状态表示当前节点为消防站,可以管理以i节点的子树以及i的爷爷
1 状态表示当前节点的儿子v为消防站,可以管理以v为根的子树和i号节点的爸爸
2 状态表示当前节点的孙子t为消防站,可以管理以t为根的子树和i号节点的爷爷
3 状态表示当前节点的重孙子ct为消防站,可以管理以ct为根的子树和ct节点的儿子
4 ...........

这是一个好博客(题解)!

code

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define maxn 2100 using namespace std ; int read() { int x = 0 , f = 1 ; char s = getchar() ; while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;} while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar() ;} return x*f ; } struct dy{ int x , y , z , next ; }a[maxn] ; int f[maxn][10] , n ; int head[maxn] , vis[maxn] , dep[maxn] , t ; int add(int x ,int y) { a[++t].x = x ; a[t].y = y ; a[t].z = 1 ; a[t].next = head[x] ; head[x] = t ; } void dfs(int now) { f[now][0] = 1 ; f[now][3] = 0 ; f[now][4] = 0 ; for(int i = head[now] ; i ; i = a[i].next) { int v = a[i].y ; dfs(v) ; f[now][0] += f[v][4] ; f[now][3] += f[v][2] ; f[now][4] += f[v][3] ; } if(!head[now]) { f[now][1] = f[now][2] = 1 ; }else { f[now][1] = f[now][2] = maxn * 10 ; for(int i = head[now] ; i ; i = a[i].next) { int v = a[i].y ; for(int j = head[now] ; j ; j = a[j].next) { if(i==j) continue ; int t = a[j].y ; f[v][0] += f[t][3] ; f[v][1] += f[t][2] ; } f[now][1] = min(f[now][1],f[v][0]) ; f[now][2] = min(f[now][2],f[v][1]) ; } } for(int i = 1 ; i <= 4 ; i ++) { f[now][i] = min(f[now][i],f[now][i-1]) ; } } int main () { n = read() ; for(int i = 2 ; i <= n ; i ++) { int x = read() ; // add(i,x) ; add(x,i) ; } dfs(1) ; printf("%d\n",f[1][2]) ; return 0 ; }