광산 탐사

Prospectin' Pete는 새로운 티타늄 광산에 대한 정보를 얻었고, 투자자에게 채굴 사업을 설명하는 데 도움이 필요하다. 이 광산은 트리로 나타낼 수 있다. 광산 입구가 루트이고, 나머지 노드는 지하의 티타늄 광석 포켓이다. 간선은 Pete가 두 포켓 사이에 팔 수 있는 터널이다(루트에 인접한 간선이라면 광산 입구와 포켓 하나 사이). $i$번째 광석 포켓과 부모를 잇는 터널의 길이는 $y_i$피트이다. 트리의 잎 중 하나에는 모티어로드가 있고, 나머지 광석 포켓에는 각각 $x_i$달러어치 광석이 있다.

Pete는 광산 입구에서 출발해 모티어로드에 도달하는 것이 목표다. 포켓 $i$로 가는 터널의 흙 $y_i$피트를 모두 걷어내기 전에는 그 포켓에 갈 수 없다. 다만 터널을 완전히 뚫은 뒤에는 양방향으로 원하는 만큼 몇 번이고 지날 수 있다.

Pete는 다음 과정을 순서대로 반복하며 광산을 탐사한다.

1. 현재 위치에서 갈 수 있고 아직 완전히 뚫리지 않은 터널 하나를 고른다.
2. 고른 터널을 1피트 판다. 비용은 1달러이다.
3. 터널이 완전히 뚫렸다면 Pete는 터널을 지나 새로 열린 포켓에 가서 광석을 캔다. 그 포켓에 모티어로드가 있으면 탐사를 멈춘다. 없다면 그 포켓의 광석을 $x_i$달러에 팔고 탐사를 계속한다.

1번 단계에서 고르는 터널은 현재 위치와 인접할 필요가 없다. 이미 뚫린 터널을 따라 그 터널까지 도달할 수 있으면 된다. 직전 라운드에 판 터널이 아직 다 뚫리지 않았더라도, 라운드마다 다른 터널을 고를 수 있다. 한 라운드를 마쳤을 때 돈이 한 푼도 없고 모티어로드에도 도달하지 못했다면 사업은 실패하고 Pete는 파산한 채 집으로 돌아간다.

Pete는 광산의 구조와 각 광석 포켓의 광석량을 알고 있지만, 아직 터널을 어떻게 파낼지 정하지 않았다. 광산 수익 외에도 모티어로드에 도달하려면 초기 자금이 필요하다는 것을 알고 있어서 투자자를 찾고 있다. 그는 투자자에게 다음 두 값을 제시하려 한다.

• 최악의 경우에도 사업이 성공하도록, 즉 매 라운드에 어떤 터널을 고르든 모티어로드에 반드시 도달하도록 Pete가 처음 가지고 있어야 할 최소 금액 $a$(달러).
• 최적으로 터널을 골랐을 때 모티어로드에 도달하기 위해 처음 가지고 있어야 할 최소 금액 $b$(달러).

투자자는 이 두 값을 보고, Pete가 실수 없이 최적으로 파낼 것이라고 얼마나 믿는지에 따라 투자금을 정할 수 있다.

광산 구조가 주어졌을 때 $a$와 $b$를 구하라.

그림 F.1: 샘플 입력 1(왼쪽)과 2의 도식이다. 간선은 터널, 노드는 광석 포켓을 나타낸다. 각 포켓의 광석 가치 $x_i$와 각 터널의 길이 $y_i$는 검은색 글씨로 적혀 있다. ML은 모티어로드를 뜻한다. 노드 번호는 빨간색으로 표시했다.

첫 줄에 정수 $n$($2 \le n \le 200000$)이 주어진다. 트리의 노드 수이다. 이어서 $n-1$개의 줄이 주어지며, $i$번째 줄에는 노드 $i$에 대한 정수 세 개 $p_i$, $x_i$, $y_i$가 주어진다. $p_i$($0 \le p_i < i$)는 노드 $i$의 부모 번호이다. 부모 번호가 0이면 부모는 광산 입구(루트)이다. $x_i$는 노드 $i$의 광석 가치이고, $y_i$($1 \le y_i \le 1000$)는 노드 $p_i$와 노드 $i$를 잇는 터널의 길이이다. $x_i = -1$인 노드는 정확히 하나이며, 그곳에 모티어로드가 있다. 나머지 값은 모두 $0 \le x_i \le 1000$을 만족한다.

노드 0은 광산 입구이다. 광석이 없고 대응하는 입력 줄도 없다. 모티어로드는 잎이라고 가정해도 된다. 즉 모티어로드를 부모로 두는 노드는 없다.

공백으로 구분한 정수 $a$와 $b$를 출력한다. 위에서 설명한 대로, 모티어로드까지 길을 뚫는 데 필요한 최악의 경우 투자금과 최선의 경우 투자금이다.

샘플 입력 1의 광산(그림 F.1의 왼쪽)을 보자. Pete가 나쁜 선택을 해도 모티어로드에 확실히 도달하려면 8달러가 필요하다. 최악의 경우 그는 먼저 2달러로 노드 2로 가는 터널을 완전히 뚫고, 이어서 5달러로 노드 4로 가는 터널을 뚫는다. 마지막 1달러로는 모티어로드까지 파고 들어가거나, 노드 1로 가는 터널을 열어 다음 라운드에 모티어로드에 도달할 자금을 얻는다. 최선의 경우에는 1달러면 충분하다. 그 1달러로 노드 1로 가는 터널을 파고, 거기서 캔 3달러어치 광석으로 입구에서 모티어로드까지 가는 경로의 터널 두 개를 판다.

그림 F.1의 오른쪽에 있는 샘플 입력 2도 같은 방식이다. 최악의 경우 한 예로, Pete는 노드 1로 가는 터널을 3피트, 노드 3으로 가는 터널을 2피트, 노드 4로 가는 터널을 1피트 판다. 이 과정에서 광석은 전혀 얻지 못하고 6달러를 쓴다. 7번째 달러로는 나머지 광산(모티어로드 포함)을 탐사할 자금을 주는 광석 포켓에 반드시 도달한다. 최선의 경우에는 1달러면 된다. 노드 2, 4, 3, 1 순서로 파 나가면 모티어로드를 찾는다.