9885번 - Claws
[문제]
그림 1과 같이, 이진 트리 형태의 중장비 구조물이 있다. (즉, 모든 비단말 노드는 최대 두 개의 자식 노드를 가진다.)트리의 간선은 금속 막대를 의미하며, 이 막대들은 힌지(관절)를 통해 연결되어 있다.트리의 각 노드는 힌지를 의미하며, 그림에서는 '1'부터 '5'까지 번호가 매겨져 있다.그림 1(a)에서 리프 노드(leaf node)는 중장비가 실제로 작업을 수행하는 클로(claw)를 의미한다.클로 역시 금속 막대와 힌지를 통해 연결되어 있다.
(그림 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까지 번호가 매겨져 있으며, 부모가 없는 노드가 루트 노드이다.
[출력]
모든 클로 중에서 최대 무부하 하중을 나타내는 정수 하나를 출력한다.
댓글을 작성하려면 로그인해야 합니다.
madirony52 11달 전 3
[문제]
그림 1과 같이, 이진 트리 형태의 중장비 구조물이 있다. (즉, 모든 비단말 노드는 최대 두 개의 자식 노드를 가진다.)
트리의 간선은 금속 막대를 의미하며, 이 막대들은 힌지(관절)를 통해 연결되어 있다.
트리의 각 노드는 힌지를 의미하며, 그림에서는 '1'부터 '5'까지 번호가 매겨져 있다.
그림 1(a)에서 리프 노드(leaf node)는 중장비가 실제로 작업을 수행하는 클로(claw)를 의미한다.
클로 역시 금속 막대와 힌지를 통해 연결되어 있다.
(그림 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까지 번호가 매겨져 있으며, 부모가 없는 노드가 루트 노드이다.
---
[출력]
모든 클로 중에서 최대 무부하 하중을 나타내는 정수 하나를 출력한다.