这道题真是非常神仙
第一眼看到题面肯定能想到状态是(dp[i][j])表示(i)这棵子树里染了(j)个黑点的最大值
最大值？
什么最大值，之后就会发现这个样子完全没有办法转移
所以我们考虑一下最后的答案长什么样子
突然感觉正着做不太好做，那就干脆反着做
如果没有分出黑点和白点，那么原来的答案，也就是树上所有任意两点之间的距离肯定是可以直接算出来的，这个可以用换根(dp)做到(O(n))
之后我们强行制造差异，那些有了差异的点肯定就没有办法计算距离加进最后的答案了，于是我们把这部分减掉
于是答案相比刚才的减掉了
(pre)是根路径前缀和，后面那一大坨东西就是非常熟悉的树上两点之间的距离，(col)是染的颜色，(0)表示白色，(1)表示黑色，(lca)就是(lca(i,j))
首先明确一下目标，我们要最大化价值，所以我们要最小化这个柿子的值
我们仔细观察一下这个柿子，你会发现一些奇妙的规律:
**如果一个点(i)满足(col_i=1)，那么(pre_i)就会在上面那个柿子里被计算(n-k)次，否则就会被计算(k)次
**
(k)就是黑点的总个数
这个自己感性理解一下就好了，就是(sum)的一些基本性质
之后问题变成求
好像一脸不可求的样子，但是根据我数据结构刷多了的经验，我们可以考虑一下一个类似差分的东西
我们凑合看一下，假设在(4)染了一个黑，那么现在对答案的贡献应该怎么算
我们设(s_i)表示(i)这棵子树内部有多少个白点
对于这个黑点来说所有可能的(lca)显然只能来自从它到根的路径上
根据一个非常简单的差分思想
这个时候答案就是
(s_4*pre_4+(s_3-s_4)*pre_3+(s_2-s_3)*pre_2+(s_1-s_2)*pre_1)
之后愉快的拆一下再合一下，变成了
(pre_1*s_1+s_2*(pre_2-pre_1)+s_3*(pre_3-pre_2)+s_4*(pre_4-pre_3))
其中(pre_1=0)，可以不用考虑
(pre)是什么啊，根路径前缀和啊，(pre_2-pre_1)是什么啊，不就是(2)到(1)那条边的边权吗
于是答案就变成了有趣的(s_2*w_2+s_3*w_3+s_4*w_4)，(w_i)表示(i)点到其父亲的边的长度
如果看到这里能理解这个差分的话，那么有一道水题可以去做一下，尽管这是一道数据结构题
我们重新回到最开始的那个柿子，现在的问题变成了如何合理分配黑点和白点，使得这个柿子的值最大
根据我们刚才的推导有这样几条规则
-
一个点(x)染成黑色，那么贡献是(pre_x*(n-k))
-
一个点(x)染成白色，那么贡献是(pre_x*k)
-
对于每条边还应统计贡献，贡献是减掉这条边的长度乘以其下面有几个白点，同时一条边可能会被这样的方式计算多次，因为这条边下方可能有好几个黑点（其实就是下面有多少个黑点算多少次）
有了这三条规则，我们就可以很轻易的设计出状态来，用(dp[i][j])表示以(i)为根的子树里染(j)个白点的最小贡献是多少
这样的话直接树形(dp)就好了，就是一个非常套路的树上背包
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define maxn 2005
#define LL long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
struct E
{
int v,nxt,w;
}e[maxn<<1];
int n,num,K;
int sum[maxn],head[maxn],deep[maxn];
LL f[maxn],pre[maxn],dp[maxn][maxn],tf[maxn];
inline void add_edge(int x,int y,int z)
{
e[++num].v=y;
e[num].nxt=head[x];
e[num].w=z;
head[x]=num;
}
inline int read()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
void dfs(int x)
{
sum[x]=1;
for(re int i=head[x];i;i=e[i].nxt)
if(!deep[e[i].v])
{
deep[e[i].v]=deep[x]+1;
tf[e[i].v]=e[i].w,pre[e[i].v]=pre[x]+e[i].w;
dfs(e[i].v);
sum[x]+=sum[e[i].v];
f[x]+=f[e[i].v],f[x]+=sum[e[i].v]*e[i].w;
}
}
void down(int x)
{
for(re int i=head[x];i;i=e[i].nxt)
if(deep[e[i].v]>deep[x])
{
f[e[i].v]+=f[x]-f[e[i].v]-sum[e[i].v]*e[i].w;
f[e[i].v]+=(n-sum[e[i].v])*e[i].w;
down(e[i].v);
}
}
void Redfs(int x)
{
dp[x][1]=-1*(LL)K*pre[x],dp[x][0]=-1*(LL)(n-K)*pre[x];
for(re int i=head[x];i;i=e[i].nxt)
if(deep[e[i].v]>deep[x])
{
Redfs(e[i].v);
for(re int j=min(n-K,sum[x]);j>=0;j--)
{
LL mid=-9893849389343;
for(re int p=0;p<=j;p++)
mid=max(mid,dp[x][j-p]+dp[e[i].v][p]);
//树上背包合并，这里将贡献值取反了，于是需要求最大值
dp[x][j]=mid;
}
}
for(re int j=0;j<=min(n-K,sum[x]);j++)
dp[x][j]+=2*tf[x]*j*(sum[x]-j);
}
int main()
{
n=read(),K=read();
int x,y,z;
for(re int i=1;i<n;i++)
x=read(),y=read(),z=read(),add_edge(x,y,z),add_edge(y,x,z);
deep[1]=1,dfs(1),down(1);//先换根dp求一下总答案
LL ans=0;
for(re int i=1;i<=n;i++)
ans+=f[i];//f[i]表示所有点到点i的距离和
ans>>=1ll;
if(!K)
{
std::cout<<ans;
return 0;
}
memset(dp,-20,sizeof(dp));
Redfs(1);
ans+=dp[1][n-K];
std::cout<<ans;
return 0;
}