题目大意

给出一个N个点的数

题目思路

看到树上问题就来补了

没想到还真是个好题

开始状态定义，定义代表以为根的子树，选择了个黑点，所达到的最大收益。

显然不可以转移，因为不知道其他的点黑点和白点选择情况，这里就有后效性了

所以考虑去除后效性【即不能对后面的状态产生影响】

显然直接计算距离是不可取的，但是对于两两之间的距离，在树上还可以用:

图片说明

表示第i条边的边权，代表一段点下子数的大小

根据这个启发，可以将状态转移定义为边的转移 :代表以i为根的子树，选择了个黑点，子树下边权贡献最大和是多少。

因为，选择多少个黑点是确定的，所以对于一个子树下，选择了多少个黑点，就可以算出来，这个边的贡献。

然后转移一下就好了

Code：

/*** keep hungry and calm CoolGuang!  ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e16+7;
const ll maxn = 2e6+700;
const int M = 1e6+8;
const ll mod= 1e15+7;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll a[maxn];
///以i为根的子数,涂了k个黑点，所有边权和最小值
ll dp[2005][2005];
ll sz[2005],t[2005];
ll n,m,p;
vector<pair<int,int>>v[maxn];
void dfs(int u,int fa){
    sz[u] = 1;
    for(auto x:v[u]){
        int e = x.first,w = x.second;
        if(e == fa) continue;
        dfs(e,u);
        for(int k=0;k<=m;k++) t[k] = -INF;
        for(int k=0;k<=min(m,sz[u]*1ll);k++){
            for(int j=0;j<=min(m,sz[e]*1ll);j++){
                if(k+j>m) break;
                ll bc = j,wc = sz[e]-j;
                t[k+j] = max(t[k+j],dp[u][k]+1ll*w*(bc*(m-bc)+1ll*wc*(n-m-wc))+dp[e][j]);
            }
        }
        for(int k=0;k<=m;k++) dp[u][k] = t[k];
        sz[u] += sz[e];
    }
}
int main(){
    read(n);read(m);
    for(int i=1;i<=n-1;i++){
        int x,y,w;
        read(x);read(y);read(w);
        v[x].push_back({y,w});
        v[y].push_back({x,w});
    }
    dfs(1,1);
    printf("%lld\n",dp[1][m]);
  return 0;

}/**
1
6
1 1
1 2
2 1
3 2
4 2
5 2
***/