C++14(g++5.4) 解法, 执行用时: 399ms, 内存消耗: 186088K, 提交时间: 2018-10-20 23:29:18

#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)


int head[N],edge_cnt;
struct edge {
	int to,w,nxt;
} E[N<<1];


void add(int x,int y,int z) {
	E[edge_cnt]= {y,z,head[x]};
	head[x] = edge_cnt++;
}
int n,K;
vector<long long>A[N],ans,tmp;
priority_queue<long long,vector<long long>,greater<long long> >q;

void dfs(int x,int f) {
	A[x].push_back(0);
	int i,j,k;
	for (i=head[x]; ~i; i=E[i].nxt) {
		int to=E[i].to,val=E[i].w;
		if (to==f) continue;
		dfs(to,x);
		int R1=(int)A[x].size(),R2=(int)A[to].size();
		for (k=0; k<R2; k++) A[to][k]+=val;
		for (j=0; j<R1; j++)
			for (k=0; k<R2; k++) {
				long long t=A[x][j]+A[to][k];
				if ((int)q.size()<K) {
					q.push(t);
				} else if (t>q.top()) {
					q.pop();
					q.push(t);
				} else {
					break;
				}
			}
		tmp.clear();
		j=0,k=0;
		int h=0;
		while (h<K && j<R1 && k<R2) {
			h++;
			if (A[x][j]>=A[to][k]) tmp.push_back(A[x][j++]);
			else tmp.push_back(A[to][k++]);
		}
		while (h<K && j<R1) h++,tmp.push_back(A[x][j++]);
		while (h<K && k<R2) h++,tmp.push_back(A[to][k++]);
		A[x]=tmp;
	}
}
//**************************************
int main() {
	mst(head,-1);
	scanf("%d %d",&n,&K);
	rep(i,2,n) {
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		add(x+1,y+1,z);
		add(y+1,x+1,z);
	}
	dfs(1,1);
	while(!q.empty()) {
		ans.push_back(q.top());
		q.pop();
	}
	while((int)ans.size() > 0) {
		printf("%lld\n",*(--ans.end())),ans.pop_back();
	}
}
//**************************************

C++11(clang++ 3.9) 解法, 执行用时: 712ms, 内存消耗: 189032K, 提交时间: 2018-03-03 21:45:16

#include<bits/stdc++.h>
#define SZ(X) (int)((X).size())
typedef long long LL;
using namespace std;
const int MAX_N = 200000;
const int MAX_K = 58311;
int N,K;
priority_queue<LL,vector<LL>,greater<LL> >ma_dises;
vector<pair<int,int> >e[MAX_N];
vector<LL>ma[MAX_N];
void read() {
	scanf("%d%d",&N,&K);
	for(int i=1; i<N; i++) {
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		e[x].push_back({y,v});
		e[y].push_back({x,v});
	}
}
void add(LL v) {
	if(SZ(ma_dises)<K)ma_dises.push(v);
	else if(v>ma_dises.top()) {
		ma_dises.push(v);
		ma_dises.pop();
	}
}
LL tmp[MAX_K*2];
void dfs(int x,int lt) {
	ma[x]=vector<LL>(1);
	for(int i=0; i<SZ(e[x]); i++) {
		int y,v;
		y=e[x][i].first;
        v=e[x][i].second;
		if(y==lt)continue;
		dfs(y,x);
		for(int j=0; j<SZ(ma[y]); j++) {
			ma[y][j]+=v;
			for(int k=0; k<SZ(ma[x]); k++) {
				add(ma[x][k]+ma[y][j]);
			}
		}
		merge(ma[x].begin(),ma[x].end(),ma[y].begin(),ma[y].end(),tmp,greater<LL>());
		ma[x]=vector<LL>(tmp,tmp+min(K,SZ(ma[x])+SZ(ma[y])));
	}
}
void solve() {
	dfs(0,0);
	vector<LL> res;
	while(SZ(ma_dises)) {
		res.push_back(ma_dises.top());
		ma_dises.pop();
	}
	for(int i=(int)res.size()-1; i>=0; i--) {
		printf("%lld\n",res[i]);
	}
}
int main() {
	read();
	solve();
	return 0;
}