madirony52   11달 전

[문제]

그림 1과 같이, 이진 트리 형태의 중장비 구조물이 있다. (즉, 모든 비단말 노드는 최대 두 개의 자식 노드를 가진다.)

트리의 간선은 금속 막대를 의미하며, 이 막대들은 힌지(관절)를 통해 연결되어 있다.
트리의 각 노드는 힌지를 의미하며, 그림에서는 '1'부터 '5'까지 번호가 매겨져 있다.

그림 1(a)에서 리프 노드(leaf node)는 중장비가 실제로 작업을 수행하는 클로(claw)를 의미한다.
클로 역시 금속 막대와 힌지를 통해 연결되어 있다.

preview

(그림 1) : (a) 트리 구조와 (b) 이에 대응되는 클로(claw) 트리 구조


이 중장비는 하중을 견디는 구조물이므로, 각 힌지는 적절한 등급(grade)을 가져야 한다. 트리의 특정 노드 v에서 사용되는 힌지의 등급은 다음 두 값의 합으로 정의된다.

(i) 노드 v를 루트로 하는 서브트리에 포함된 모든 금속 막대의 총 무게
(ii) 노드 v에서 트리의 루트까지 이어지는 경로상의 모든 금속 막대의 총 무게

그림 1에 각 금속 막대의 무게가 간선 옆에 표시되어 있다. 클로와 힌지는 매우 가벼운 재질로 만들어졌기 때문에, 무게는 0이라고 가정한다.

그림 1에서 리프 노드 1, 2, 3에서 클로를 연결하는 힌지의 등급은 각각 [노드 1 → 50, 노드 2 → 30, 노드 3 → 50]이다.
또한, 노드 4의 힌지 등급은 60, 루트 노드 5의 힌지 등급은 110이다.


하나의 클로에 대한 무부하 하중(unladen load)은 해당 클로에서 루트 노드까지 경로에 포함된 모든 힌지 등급의 합이다.

이 예제에서 각 클로의 무부하 하중은 다음과 같다.
[클로 1 → 220, 클로 2 → 200, 클로 3 → 160]

주어진 중장비(이진 트리)에 대해, 모든 클로 중에서 가장 큰 무부하 하중을 출력하라.

---

[입력]

첫 줄에 이진 트리의 전체 노드 수가 정수 n (1 ≤ n ≤ 12,000)으로 주어진다.

다음 n − 1개의 줄에는 각각 세 개의 정수가 주어진다:
thisnode : 현재 노드 번호
parnode : 부모 노드 번호
weight : 현재 노드와 부모 노드를 연결하는 금속 막대의 무게 (양의 정수, ≤ 100)

노드는 1부터 n까지 번호가 매겨져 있으며, 부모가 없는 노드가 루트 노드이다.

---

[출력]

모든 클로 중에서 최대 무부하 하중을 나타내는 정수 하나를 출력한다.

댓글을 작성하려면 로그인해야 합니다.