今天是学习DP的第二天，我的天哪，简直要S了。废话不多说，今天学习的是树形DP。树形DP，顾名思义，就是在一颗树上做DP（啥？在树上做DP？不怕摔死？？？）
    好了，不闹了。做树形DP一般都要用DFS来扫描树，然后从底部叶子开始，在回溯到根的过程中进行DP。大体思路根填表法类似，只不过是在树上进行的。所以，它的大体程序长这样：

void dp_tree(int point,int fa)
{
    for (int i=0;i<=tree.size();i++)
    {
        int nxt=tree[point][i];
        if (vis[nxt]) return
        dp_tree(nxt,point);
        # DP Code #
    }
 } 

当然，老样子，有其它条件可以自己增加维度。
    如果是刚刚开始学习，建议先做做下面两道题，都很经典：

没有上司的舞会 二叉苹果树

如果已经有一定水平，可以去看看这道题：

[HNOI2003]消防局的设立

我这里把这道题的代码放出来，还是挺长的，毕竟是道蓝题。

#include<bits/stdc++.h>
#define MAXN 1005
using namespace std;
int pnt[MAXN],nextx[MAXN*MAXN],v[MAXN*MAXN];
int f[MAXN][5];
int n,m;
int x,tot;
void init()
{
    memset(pnt,-1,sizeof(pnt));
    memset(nextx,-1,sizeof(nextx));
    tot=-1;
}
void edge(int x,int y)
{
    tot++;nextx[tot]=pnt[x];pnt[x]=tot;v[tot]=y;
    tot++;nextx[tot]=pnt[y];pnt[y]=tot;v[tot]=x;
}
void dp(int x,int fa)
{
    int ans1=INT_MAX;
    int ans2=INT_MAX;
    if(nextx[pnt[x]]==-1&&x!=1)
    {
        f[x][0]=1;
        f[x][1]=1;
        f[x][2]=1;
        f[x][3]=0;
        f[x][4]=0;
        return;
    }
    for(int i=pnt[x];i!=-1;i=nextx[i])
    if(v[i]!=fa) dp(v[i],x);
    for(int i=pnt[x];i!=-1;i=nextx[i])
    {
        if(v[i]==fa) continue;
        f[x][2]+=f[v[i]][4];
        f[x][3]+=f[v[i]][0];
        f[x][4]+=f[v[i]][3];
        ans1=min(ans1,f[v[i]][2]-f[v[i]][3]);
        ans2=min(ans2,f[v[i]][1]-f[v[i]][0]);
    }
    f[x][0]=f[x][3]+ans2;
    f[x][1]=f[x][4]+ans1;
    f[x][2]++;
    f[x][3]=min(min(f[x][3],f[x][2]),min(f[x][1],f[x][0]));
    f[x][4]=min(min(f[x][0],min(f[x][4],f[x][3])),min(f[x][2],f[x][1]));
    f[x][0]=min(f[x][0],min(f[x][1],f[x][2])); 
    f[x][1]=min(f[x][1],f[x][2]);
}

int main()
{
    cin>>n;
    init();
    for(int i=1;i<n;++i)
    {
        cin>>x;
        edge(i+1,x);
    }
    dp(1,0);
    cout<<f[1][0]<<endl;
    return 0;
}

    当然，做完题后写解题记录也是一个好习惯。所以，我决定每天解题记录打卡！这是今天的：

    好，今天的日记就到这里，我们明天见！！！