思路：
AC代码：
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define ll long long #define endl (" ") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ft (frist) #define sd (second) #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=1e6+100; const ll mod=1e9+7; ll siz[N],head[N],nex[N<<1],to[N<<1],wi[N<<1],tot,n,k; ll ans; void dfs(int u, int f, ll w){ siz[u]=1; for(int i=head[u]; i!=-1; i=nex[i]){ int v=to[i]; if(v==f) continue; dfs(v,u,wi[i]); siz[u]+=siz[v]; } if(siz[u]>=k) ans+=w*k; else ans+=w*siz[u]; } void add(int u, int v, int w){ to[tot]=v; nex[tot]=head[u]; wi[tot]=w; head[u]=tot++; } int main(){ while(scanf("%d %d",&n, &k)!=EOF){ mem(head,-1),tot=0; int u,v; ll w; for(int i=1; i<n; ++i){ scanf("%d %d %lld", &u, &v, &w); add(u,v,w); add(v,u,w); } ans=0; dfs(1,1,0); printf("%lld ",ans); } return 0; }