서브트리의 비용

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

요약
가중치가 있는 간선으로 이루어진 트리에서, 간선 개수와 그 안 최솟값의 곱이 최대가 되는 연결된 간선 집합을 찾는다.
난이도

어려움10점 중 8점

유형
트리, 유니온 파인드, 정렬, 그리디
정답자
아직 제출이 없습니다

문제

Byteazar의 집 근처에는 nn개의 정점을 가진 값진 나무가 자란다. 간선 ii에는 비용 viv_i가 부여되어 있다.

나무의 서브트리란 간선들의 공집합이 아닌 연결된 부분집합을 뜻한다.

서브트리의 비용은 서브트리에 속한 간선의 개수에 그 안에서 가장 작은 viv_i 값을 곱한 값이다.

Byteazar는 서브트리를 팔아 돈을 벌고 싶어 하므로, 자신의 나무에서 서브트리 비용의 최댓값을 알고 싶어 한다.

입력

첫째 줄에 정수 nn이 주어진다. (2≤n≤1052 \le n \le 10^5) 이는 나무의 정점 개수이다. 이어지는 n−1n-1개의 줄에는 각각 세 정수 aia_i, bib_i, viv_i가 주어진다. (1≤ai,bi≤n1 \le a_i, b_i \le n; ai≠bia_i \ne b_i; 1≤vi≤1091 \le v_i \le 10^9) 이는 간선이 연결하는 두 정점과 그 간선의 비용이다.

출력

주어진 나무의 서브트리 비용의 최댓값을 정수 하나로 출력한다.

예제2

  1. 예제 1

    입력
    10
6 4 8
5 6 7
2 3 5
3 1 2
2 7 3
9 7 4
8 2 6
8 10 7
6 2 4
    예상 출력
    24

  2. 예제 2

    입력
    6
1 3 12
5 3 4
3 4 2
2 4 5
6 2 6
    예상 출력
    12