Maximum Weighted Matching on a Tree‐Derived Complete Graph

You are given a tree \(T\) with \(n\) vertices, where each edge has a positive weight. In the complete graph \(G\) on \(n\) vertices, the weight of an edge connecting vertices \(u\) and \(v\) is defined to be the distance between \(u\) and \(v\) in \(T\) (i.e. the sum of weights along the unique path connecting them in \(T\)). For every \(i = 1, 2, \dots, \lfloor \frac{n}{2} \rfloor\), compute the maximum total weight of a matching of exactly \(i\) edges in \(G\).

A matching is a set of pairwise disjoint edges (i.e. no vertex is used more than once). The answer for a given \(i\) is the maximum sum of distances corresponding to the \(i\) chosen pairs.

inputFormat

The first line contains a single integer \(n\) (\(2 \le n \le 20\)) — the number of vertices in the tree \(T\). Each of the following \(n-1\) lines contains three integers \(u\), \(v\) and \(w\) (\(1 \le u,v \le n\), \(1 \le w \le 10^9\)), indicating that there is an edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

Output \(\lfloor \frac{n}{2} \rfloor\) numbers. The \(i\)th number should be the maximum total weight of a matching of exactly \(i\) edges in \(G\).

sample

2
1 2 5

5