E75【模板】树上背包 P2015 二叉苹果树

// 树上背包 O(n*m)
#include<bits/stdc++.h>//容易理解
using namespace std;
const int N=5010;
vector<pair<int,int>>G[N];
int n,m,f[N][N],siz[N];
void dfs(int x,int fa)
{
    siz[x]=1;
    for(auto i:G[x])
    {
        int y=i.first,c=i.second;if(y==fa)continue;
        dfs(y,x);siz[x]+=siz[y];
        for(int i=min(m,siz[x]); i>=1; i--)
            for(int j=min(i-1,siz[y]); j>=0; j--)
                f[x][i]=max(f[x][i], f[x][i-j-1]+f[y][j]+c);
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,x,y,c;i<n;i++)
    {
        cin>>x>>y>>c;
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }
    memset(f,0,sizeof(f));memset(siz,0,sizeof(siz));
    dfs(1,0);
    cout<<f[1][m]<<"\n";
    return 0;
}

#include <bits/stdc++.h> //推荐使用
using namespace std;
const int N = 5010;
vector<pair<int, int>> G[N];
int f[N][N], v[N], id, siz[N], rdfn[N];
void dfs(int x, int fa){
    siz[x] = 1;
    for (auto i : G[x]){
        int y = i.first, c = i.second;if (y == fa) continue;
        v[y] = c;
        dfs(y, x);
        siz[x] += siz[y];
    }
    rdfn[++id] = x;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, m;cin >> n >> m;m++;
    for (int i = 1, x, y, c; i < n; i++){
        cin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
    id = 0;dfs(1, 0);
    for (int i = 1; i <= id; ++i){
        int x = rdfn[i];
        for (int j = 0; j <= m; ++j){
            f[i][j] = f[i - siz[x]][j];
            if (j >= 1) f[i][j] = max(f[i][j], f[i - 1][j - 1] + v[x]);
        }
    }
    cout << f[id][m] << "\n";
    return 0;
}