34944번 - 트리의 최대 비용

문제

정점이 $N$개인 가중치 있는 트리가 주어진다.

트리에서 어떤 정점 $s$에서 시작해 어떤 정점 $e$까지 최단경로로 이동한다고 하자. 트리에서 간선을 타고 정점 $u$에서 정점 $v$로 이동할 때마다, 해당 간선의 가중치 $w$를 시작 정점 $s$에서 정점 $v$까지의 거리(간선의 개수)에 곱한 값이 경로의 비용에 합산된다. 이 비용을 $cost(s, e)$라 하자.

모든 가능한 $(s, e)$ 순서쌍을 고려할 때, $cost(s, e)$의 최대값을 출력하라. $s = e$인 경우도 고려한다.

입력

첫 번째 줄에 정수 $N$이 주어진다. (2ドル \le N \le 10^5$)

두 번째 줄부터 $N-1$개의 줄에 걸쳐 각 줄마다 트리의 간선을 나타내는 양끝 정점 $u,ドル $v$와 가중치 $w$가 차례대로 주어진다. (1ドル \le u, v \le N,ドル $-10^6 \le w \le 10^6$)

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 답을 출력한다.

제한

노트