18912번 - Funny Salesman 다국어

You are given a tree, and each edge has a non-negative integer weight.

Let $d(u, v)$ --- The maximum of the edge weights on the unique simple path between vertices $u$ and $v$.

Find the largest $\sum_{i=2}^n{2^{d(p_{i - 1}, p_i)}}$ among all permutations of vertices $p_1, p_2, \ldots, p_n$.

The first line contains one integer $n$ ($2 \leq n \leq 100\,000$): the number of vertices in the tree.

Each of the next $n-1$ lines contains three integers $u,v,w$ ($1 \leq u, v \leq n, 0 \leq w \leq 30$), an edge in the tree with endpoints $u,v$ having weight $w$.

Print one integer: the largest $\sum_{i=2}^n{2^{d(p_{i - 1}, p_i)}}$.

In the first example, one of the optimal permutations is $\{4, 5, 3, 2, 1\}$.