Funny Salesman

시간 제한1초메모리 제한512 MB

요약

가중치가 30 이하인 간선을 가진 트리에서 모든 정점을 한 번씩 나열해 연속한 두 정점 사이 경로의 최대 간선 가중치에 대한 2의 거듭제곱 합을 최대로 만든다.

난이도: 보통10점 중 7점
유형: 그리디, 트리, DFS, 정렬
정답자: 아직 제출이 없습니다

문제

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\\}$ .

예제2

예제 1
입력
```
5
1 2 0
2 3 0
3 4 0
4 5 1
```
예상 출력
```
6
```

예제 2

입력

예상 출력