樹形DP——Luogu2014 選課

題面：傳送門

首先顯然的這個樹形結構的東西是一個森林

我們随便搞一個超級彙點變成一棵樹好了

然後問題來了，這棵樹是多叉樹……

我想的狀态是這樣的：f[i][j]表示在以i節點為根的子樹内取j個（符合題意）的最大值

轉移的時候把子樹内的轉移到這棵子樹的根即可，隻不過這個根必選

可惜的是如果按照多叉樹來轉移的話轉移會很麻煩。。。

是以隻能多叉轉二叉了，也就是說左兒子右兄弟

然後就可以用上面轉移的方法轉移了

對于超級彙點來說，因為按照上面轉移，超級彙點也必須選上（你也可以特判）

是以最後答案是f[超級彙點][m+1]

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<climits>
#include<ctime>
#include<string>
using namespace std;
int n,m,ls[],rs[],v[],s[];
int nedge=,p[],nex[],head[];
int f[][];
inline void addedge(int a,int b){
    p[++nedge]=b;nex[nedge]=head[a];head[a]=nedge;
}
inline void dfs(int x){//多叉轉二叉
    int k=head[x];
    if(!k)return;
    ls[x]=p[k];dfs(p[k]);
    int pp=p[k];
    for(k=nex[k];k;k=nex[k]){
        rs[pp]=p[k];dfs(p[k]);
        pp=p[k];
    }
}
inline void dp(int x){//樹形DP
    if(!x)return;
    dp(ls[x]),s[x]+=s[ls[x]];
    dp(rs[x]),s[x]+=s[rs[x]];
    s[x]++;
    for(int i=;i<=s[x];i++){
        f[x][i]=i>s[rs[x]]?:f[rs[x]][i];
        for(int j=;j<=min(s[ls[x]],i-);j++){
            if(i-j->s[rs[x]])continue;
            int l=f[ls[x]][j],r=f[rs[x]][i-j-];
            f[x][i]=max(f[x][i],l+r+v[x]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++){
        int x;scanf("%d%d",&x,&v[i]);
        if(x==)x=n+;
        addedge(x,i);
    }
    dfs(n+);dp(n+);
    printf("%d",f[n+][m+]);
    return ;
}