第一道树形dp。挺奇怪的。

---

这道题选择一个点是有一个先决条件，也就是要先选他父亲的点。

画出草图可以发现就是森林嘛。。。

利用网络流的思想，建立超级根结点，把以0为父亲的都连到root去。

树形dp较线性dp的不同之处就是要dp儿子。

所以在树上要dp之前先弄一下儿子，确保他已经被dp好了就可以了。

如何实现？dfs！

在dfs中套出这么一个板子就可以了。

树形dp老思路：

设dp[i][j]为在第i个结点的子树中，选择j个结点的最大或最小花费。

然后一般就有：

dp[i][j] = dp[i][j - k] + dp[son][k]

k是在子树中弄的，所以从1到子树size-1。

因为类似于01背包，所以要逆序递推。

代码：

#include
    
     #include
     
      const int maxn = 3005;struct Edges{    int next, to;} e[maxn << 2];int head[maxn], tot;int n, m;int dp[maxn][maxn];int root;void link(int u, int v){    e[++tot] = (Edges){head[u], v};    head[u] = tot;}int dfs(int u){    int ans = 1;    for(int i = head[u]; i; i = e[i].next)    {        int v = e[i].to;        int t = dfs(v);        ans += t;        for(int j = ans; j > 0; j--)        {            for(int k = 0; k <= t; k++)            {                if(j - k > 0) dp[u][j] = std::max(dp[u][j], dp[u][j - k] + dp[v][k]);            }        }    }    return ans;}int main(){    //for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++) dp[i][j] = -19260817;    scanf("%d%d", &n, &m);    root = n + 1;    for(int i = 1; i <= n; i++)    {        int k; scanf("%d%d", &k, &dp[i][1]);        if(k == 0) k = root;        link(k, i);    }    dfs(root);    printf("%d\n", dp[root][m + 1]);    return 0;}