시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1536 MB48282356.098%

문제

정점이 $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$)

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

출력

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

예제 입력 1

2
1 2 3

예제 출력 1

3

예제 입력 2

4
1 2 1
1 3 2
2 4 3

예제 출력 2

13

예제 입력 3

7
1 2 1
1 3 2
2 4 3
3 5 4
3 6 5
6 7 6

예제 출력 3

61

출처

University > 서울사이버대학교 > 2025 서울사이버대학교 프로그래밍 경진대회 (SCUPC) K번