마을 N개가 N-1개의 길로 이어져 있다.

즉, 마을들은 트리 형태로 이루어져 있다.

준혁이는 1번 마을에서 시작해서 2번 마을, 3번 마을, ... , N번 마을을 순서대로 방문할 것이다.

각 길을 지나기 위해서는 통행권이 필요한데, 통행권에는 해당 길을 한 번 지나갈 수 있는 1회 통행권과, 해당 길을 몇 번이든 지나갈 수 있는 다회 통행권이 존재한다.

i번째 길의 1회 통행권의 가격은 P_i이고, 다회 통행권의 가격은 Q_i이다.

준혁이가 마을들을 순서대로 방문하기 위해 통행권을 구입하는데 필요한 최소 금액을 구하여라.

간단한 트리 문제 timer 1000초 memory 512MB

간단한 트리 문제 1000초 512MB