P9047 [PA 2021] Tax Collectors

Given a tree with $n$ vertices, you may choose several pairwise disjoint paths of length $4$ (meaning $4$ edges) (**you may also choose none**). For a chosen set of paths, the profit is the sum of edge weights in the union of all chosen paths. Find the maximum profit.

The first line contains an integer $n$. The next $n - 1$ lines each contain three integers $u, v, w$, describing an edge $(u, v)$ in the tree with weight $w$.

Output one line with one integer, the required value.

#### Explanation of Sample #1 One optimal solution is to choose the paths $2 \to 6$, $6 \to 10$, $11 \to 15$, $16 \to 19$. #### Explanation of Sample #2 Since the weight of every length $4$ path is negative, choosing none is optimal. #### Constraints For $100\%$ of the testdata, $2 \leq n \leq 2 \times 10^5$, and $-10^9 \leq w_i \leq 10^9$. Translated by ChatGPT 5