트리 꾸미기 timer 1s memory - MB

농부 창호는 자신이 가지고 있는 "봄 추수 트리"(크리스마스 트리와 같지만 크리스마스 3달 뒤에 주로 사용된다) 를 꾸미려고 한다.

이는 N (1≤N≤100,000)개의 원소로 이뤄진 루트를 가진 수학적인 트리(맨 아래 설명 참조)로 구성되어 있으며, 각 원소에는 1번 부터 N번까지의 번호가 붙어있다.

1번 원소는 루트라 한다.

번호가 1번 보다 큰 모든 원소들을 e라고 할때, 이러한 원소들은 부모를 가지고 있으며, 이는 P_e(1≤P_e≤N) 라고 한다.

1번 원소는 루트이기 때문에 부모가 존재하지 않는다( 입력이 주어질 때 P1=-1로 주어진다 ).

각 원소들은 자신을 루트로 한 서브 트리를 가지고 있다( 서브 트리의 크기는 최소 1이다 ).

창호는 i번 노드에 대응되는 서브트리에 최소 C_i (0≤C_i≤10,000,000)개의 장식을 설치하려고 한다.

또한 창호는 장식을 설치하는데 드는 시간의 합을 최소화 하려고 한다. (만약 K개의 장식을 i번 노드에 설치할 떄 K*T_i의 시간이 걸린다(1≤T_i≤100 ).

창호가 원하는 데로 장식을 할 수 있는 프로그램을 작성하라. 답은 2⁶³-1 이하라고 가정한다.

예를 들어 아래와 같이 위에 배치된 노드가 아래에 배치된 노드의 부모인 트리가 있다고 가정하자(1번 노드가 루트이다).

창호가 다음과 같이 서브트리에 대한 제약을 정했다고 하자:

창호는 아래와 같이 모든 장식을 아래와 같이 놓을 수 있으며, 이 경우 전체 비용은 20이 된다.

노드 번호 [ 해당 노드에 위치한 장식물의 개수 /해당 노드의 서브 트리 내의 장식물의 개수(노드에 장식물을 설치하기위한 시간) ]