LUOGU P2015 二叉苹果树

传送门

解题思路

树形背包，dp[x][i] 表示以x为根的子树留i个树枝的最大值。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
const int MAXN = 105;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}

int n,q,head[MAXN],cnt,dp[MAXN][MAXN];
int to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1];

inline void add(int bg,int ed,int w){
    to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=w,head[bg]=cnt;
}

int dfs(int x,int pre){
    int sum=0;
    for(register int i=head[x];i;i=nxt[i]){
        int u=to[i];if(u==pre) continue;
        sum+=dfs(u,x)+1;
    }
    for(register int i=head[x];i;i=nxt[i]){
        int u=to[i];if(u==pre) continue;
        for(register int j=sum;j;j--)   
            for(register int k=0;k<j;k++)
                dp[x][j]=max(dp[x][j],dp[u][k]+dp[x][j-k-1]+val[i]);
    }
    return sum;
}

int main(){
    n=rd(),q=rd();int x,y,z;
    for(register int i=1;i<n;i++){
        x=rd(),y=rd(),z=rd();
        add(x,y,z),add(y,x,z);
    }
    dfs(1,0);cout<<dp[1][q];
    return 0;
}