#P18655. MIT

MIT

MIT

给定一棵有 nn 个顶点、边上带权的树 TT。定义 duvd_{uv} 为 TT 中从顶点 uu 到顶点 vv 的唯一简单路径上所有边权之和。

建立一个有相同顶点集合的完全无向带权图 GG,其中边 (u,v)(u,v) 的权值为 duvd_{uv}。

对每个 k=1,2,…,⌊n/2⌋k=1,2,\ldots,\lfloor n/2\rfloor,求 GG 中恰好包含 kk 条边的匹配的最大权值和。包含 kk 条边的匹配指一组 kk 条边,其中任意两条边都没有公共端点。

输入格式

第一行包含一个整数 nn(2≤n≤1000002\le n\le100000),表示树的顶点数。

接下来 n−1n-1 行描述树边。每行包含三个整数 ui,vi,wiu_i,v_i,w_i,表示顶点 ui,viu_i,v_i 之间有一条权值为 wiw_i 的边:

1≤ui,vi≤n,1≤wi≤108.1\le u_i,v_i\le n,\qquad 1\le w_i\le10^8.

保证输入边构成一棵树。

输出格式

输出 ⌊n/2⌋\lfloor n/2\rfloor 个整数,依次表示大小为 1,2,…,⌊n/2⌋1,2,\ldots,\lfloor n/2\rfloor 的匹配的最大权值和。

样例输入

7
1 3 99
2 3 82
3 4 4
4 5 43
5 6 5
4 7 3

样例输出

181 280 287