10153. 「一本通 5.2 例 1」二叉苹果树

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    char ch=getchar();ll res=0,f=1;
    while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
ll n,Q,f[110][110],a[110],l[110],r[110],mp[110][110];
void MakeTree(int x){
    for(int i=1;i<=n;i++){
        if(mp[x][i]!=-1){
            l[x]=i;a[i]=mp[x][i];
            mp[x][i]=mp[i][x]=-1;
            MakeTree(i);
            break; 
        }
    }//Make Left Son
    for(int i=1;i<=n;i++){
        if(mp[x][i]!=-1){
            r[x]=i;a[i]=mp[x][i];
            mp[x][i]=mp[i][x]=-1;
            MakeTree(i);
            break;
        }
    }//Make Right Son
}
int DP(int x,int j){

    if(j==0){f[x][j]=0;return 0;}
    if((!l[x])&&(!r[x])){f[x][j]=a[x];return a[x];}
    if(f[x][j]>0) return f[x][j];
    for(int k=0;k<j;k++) f[x][j]=max(f[x][j],DP(l[x],k)+DP(r[x],j-k-1)+a[x]);
    return f[x][j];
}
int main(){
    n=read();Q=read();Q++;
    memset(mp,-1,sizeof(mp));
    for(int i=1;i<=n-1;i++){
        int x=read(),y=read(),z=read();
        mp[y][x]=mp[x][y]=z;
    }
    MakeTree(1);
    write(DP(1,Q));putchar('\n');
    /*
    cout<<"-----------------------------------"<<endl;
    for(int i=1;i<=n;i++){
        cout<<"Node "<<i<<":\n";
        cout<<"Left Son:"<<l[i]<<" Right Son:"<<r[i]<<endl;
        cout<<"Val:"<<a[i]<<endl;
        cout<<"DP :\n";
        for(int j=0;j<=Q;j++){
            cout<<"Has "<<j<<":"<<f[i][j]<<endl;
        }
        cout<<endl;
    } 
    */
    return 0;
}
//设f[i][j]表示以i为根节点，保留j个节点的最大苹果数量
//f[i][j]=max{f[l[i]][k]+f[r[i]][j-k-1]+a[i]}(0<=k<=j-1) 
//f[i][j]=0(0<i<=n,0<=j<=Q+1)
//f[i][j]=a[i](j!=0&&l[i]==0&&r[i]==0)
//Answer:f[1][Q+1]
/*
Sample Input:
5 2
1 3 1
1 4 10
2 3 20
3 5 20
Sample Output:
21
*/