一个很摸不清头脑的树形dp

状态：

$ dp[i][0] $ :选自己

$ dp[i][1] $ :选了至少一个儿子

$ dp[i][2] $ :选了至少一个孙子

-----------------------------------覆盖了自己的

$ dp[i][3] $ : 儿子孙子全部覆盖

$ dp[i][4] $ :孙子全部覆盖

-----------------------------------并没有覆盖自己

初始转移方程：

$ dp[i][0] = 1+\sum min(dp[j][0...4]) $ ;

要使选了根节点之后合法（整棵子树包括根节点被覆盖）必须使儿子的孙子全部覆盖， 0~4状态满足

$ dp[i][1] = min( dp[k][0] + \sum min(dp[j][0...3](j != k)) ) $ ;

要使选了一个儿子之后合法 由于儿子只可以覆盖到兄弟 所以孙子一定要全部被覆盖 即儿子的儿子一定覆盖 0~3满足

$ dp[i][2] = min( dp[k][1] + \sum min(dp[j][0...2](j != k)) ) $ ;

使选了一个孙子之后合法 由于孙子最多只能覆盖到当前节点 所以儿子一定全部覆盖 即所有儿子本身要被覆盖 0~2满足

$ dp[i][3] = \sum dp[j][0...2] $ ;

要使儿子及孙子全部被覆盖 即儿子本身要被覆盖 0~2满足

$ dp[i][4] = \sum dp[j][0...3]; $

要使孙子全部被覆盖 即儿子的儿子要全部被覆盖 0~3满足

注意：

每种状态由儿子转移过来所以根的情况 要转化成对于儿子来说的情况

然后改进状态 因为每种转移方程至少有三种可能最后取其中较小的 故时间效率较低

令 $ dp[i][k] $ 表示 $ min(dp[i][0],dp[i][1]....dp[i][k]) $ 且 $ k>=2 $ 因为上述转移方程最少都是0~2状态

那么转移方程就大幅度化简了：

$ dp[i][0] = 1+\sum dp[j][4] $ ;

直接由上面变形而来

$ dp[i][1] = dp[i][4] + min(dp[k][0]-dp[k][3]) $ ;

选一个儿子 需保证所有孙子被覆盖 即 $ dp[i][4] $ 然后要选出一个儿子 将他从0~3状态变为选了自己（由于 $ dp[i][4] $ 中他是3状态所以要减去一个 $ dp[k][3] $ ） 取这个差值最小的儿子

$ dp[i][2] = dp[i][3] + min(dp[k][1]-dp[k][2]) $ ;

选一个孙子 与上面类似 要保证所有儿子都被覆盖 即 $ dp[i][3] $ 再将一个儿子从0~2状态变为0~1状态以保证覆盖他父节点

$ dp[i][3] = \sum dp[j][2] $ ;

保证所有儿子被覆盖 儿子的0~2状态均符合条件

$ dp[i][4] = \sum dp[j][3] $ ;

保证所有儿子的儿子被覆盖 儿子的0~3状态均符合条件

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 1005;inline int read(){    char ch = getchar();    int f = 1 , x = 0;    while(ch > '9' || ch < '0' ){if(ch == '-')f = -1;ch = getchar();}    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}    return x * f;}int n,a[maxn][maxn];int f[maxn][5];int main(){    n = read();    for(int i=2;i<=n;i++){        int x;  x = read();        a[x][i] = 1;    }    for(int i=n;i>=1;i--){        int x1 = 1e8 , x2 = 1e9;        f[i][0] = 1;        for(int j=1;j<=n;j++){            if(a[i][j]){                f[i][0] += f[j][4];                f[i][3] += f[j][2];                f[i][4] += f[j][3];                x1 = min(x1 , f[j][0] - f[j][3]);                x2 = min(x2 , f[j][1] - f[j][2]);            }        }        f[i][1] = f[i][4] + x1;        f[i][2] = min(f[i][3] + x2 , min(f[i][0] , f[i][1]));        f[i][3] = min(f[i][2] , f[i][3]);        f[i][4] = min(f[i][3] , f[i][4]);    }    printf("%d",f[1][2]);    return 0;}