题解
树形dp呐。
对于节点\(x\)，每去向它的一个子结点，经过\(x\)的次数便会\(+1\)。因此如果最后回到\(x\)的话，最多可以去向\(k-1\)个子节点。但如果最后停留在\(x\)的子树当中，最多便可去向\(k\)个子节点。
状态：\(dp[i][j]\)表示以节点\(i\)为根的子树，是/否（\(j=1/0\)）在其中结束时的边权最大和。
转移：设\(i\)的子结点个数为\(x\)，\(j\)为\(i\)的子节点。\(dp[i][0]=dp[j][0]\)中最大的\(k-1\)个。\(dp[i][1]\)有2种情况：①在\(dp[i][0]\)前\(k\)大的子节点子树中结束，\(dp[i][1]=dp[i][0]+\)前\(k\)个节点中\(max(dp[j][1]-dp[j][0])+\)第\(k\)大的\(dp[j][0]\)；②在其他子节点子树结束，\(dp[i][1]=dp[i][0]+\)其他节点中\(max(dp[j][1])\)。优先队列维护子节点\(dp\)值即可。
目标状态：\(dp[0][1]\)（易得\(dp[0][1]\ge dp[0][0]\)）
AC代码
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1e5+10;
int fst[N],nxt[2*N],v[2*N],w[2*N],cnt;
int dp[N][2],ans,k;
void add(int x,int y,int z)
{
v[++cnt]=y,w[cnt]=z;
nxt[cnt]=fst[x],fst[x]=cnt;
}
void dfs(int x,int fa)
{
int tmp=0,qwq,qaq;
priority_queue<pair<int,int> > q;
for(int i=fst[x];i;i=nxt[i])
{
int y=v[i];
if(y==fa) continue;
dfs(y,x); q.push(mp(dp[y][0]+w[i],y));
}
for(int i=1;i<k && !q.empty();i++)
{
dp[x][0]+=q.top().first; qwq=q.top().second;
tmp=max(tmp,dp[qwq][1]-dp[qwq][0]); q.pop();
}
if(q.empty()) {dp[x][1]=dp[x][0]+tmp; return;}
qwq=q.top().second;
tmp=max(tmp,dp[qwq][1]-dp[qwq][0])+q.top().first;
while(!q.empty())
{
qwq=q.top().second,qaq=q.top().first; q.pop();
tmp=max(tmp,qaq+dp[qwq][1]-dp[qwq][0]);
}
dp[x][1]=dp[x][0]+tmp;
}
int main()
{
int n,x,y,z;
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
dfs(0,-1);
printf("%d",dp[0][1]);
return 0;
}