CF802K Send the Fool Further!（Jan. 22th, 2019） 树形DP

// La Pluie
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
typedef long long ln;
vector <ln> e[N], w[N];
pair<ln,ln> q[N];
ln n,k,dp[N][2];
void dfs(int u,int f){
    int t=0,l=e[u].size();
    for(int i=0;i<l;i++)
        if(e[u][i]!=f) dfs(e[u][i],u);
    for(int i=0;i<l;i++){
        if(e[u][i]!=f){
            int v=e[u][i];
            q[++t]=make_pair(dp[v][1]+w[u][i],v);
        }
    }
    sort(q+1,q+t+1);
    reverse(q+1,q+t+1);
    if(t<k){
        ln mx=0;
        for(int i=1;i<=t;i++){
            int v=q[i].second;
            dp[u][1]+=q[i].first;
            mx=max(mx,dp[v][0]-dp[v][1]);
        }
        dp[u][0]=dp[u][1]+mx;
    }
    else{
        ln sum=0;
        for(int i=1;i<=k;i++){
            if(i<k) dp[u][1]+=q[i].first;
            sum+=q[i].first;
        }
        for(int i=1;i<=t;i++){
            int v=q[i].second;
            if(i<=k) dp[u][0]=max(dp[u][0],sum+dp[v][0]-dp[v][1]);
            else dp[u][0]=max(dp[u][0],sum+(dp[v][0]+(q[i].first-dp[v][1]))-q[k].first);
        }
    }
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<n;i++){
        ln u,v,W;
        scanf("%lld%lld%lld",&u,&v,&W);
        u++,v++;
        e[u].push_back(v);
        e[v].push_back(u);
        w[v].push_back(W);
        w[u].push_back(W);
    }
    dfs(1,0);
    printf("%lld",max(dp[1][0],dp[1][1]));
    return 0;
}