MIT
给定一棵有 n 个顶点、边上带权的树 T。定义 duv 为 T 中从顶点 u 到顶点 v 的唯一简单路径上所有边权之和。
建立一个有相同顶点集合的完全无向带权图 G,其中边 (u,v) 的权值为 duv。
对每个 k=1,2,…,⌊n/2⌋,求 G 中恰好包含 k 条边的匹配的最大权值和。包含 k 条边的匹配指一组 k 条边,其中任意两条边都没有公共端点。
输入格式
第一行包含一个整数 n(2≤n≤100000),表示树的顶点数。
接下来 n−1 行描述树边。每行包含三个整数 ui,vi,wi,表示顶点 ui,vi 之间有一条权值为 wi 的边:
1≤ui,vi≤n,1≤wi≤108.
保证输入边构成一棵树。
输出格式
输出 ⌊n/2⌋ 个整数,依次表示大小为 1,2,…,⌊n/2⌋ 的匹配的最大权值和。
样例输入
7
1 3 99
2 3 82
3 4 4
4 5 43
5 6 5
4 7 3
样例输出
181 280 287