KOI 나라는 N개의 도시로 이루어져 있으며, 각 도시는 1, 2, \cdots , N의 번호가 매겨져 있다. 1번 도시는 KOI 나라의 수도이다.

KOI 나라에는 N - 1개의 양방향 도로가 있으며, 2 ≤i ≤ N인 모든 i에 대해, i번 도시는 P_i번 도시와 양방향 도로로 연결되어 있다.

이 때, P_i <i 를 만족하며, i번 도시와 P_i번 도시를 잇는 도로의 일일 이용량은 W_i이다.

1번 도시(수도)에서 v번 도시를 잇는 단순 경로 위에 u번 도시가 있다면, 우리는 u번 도시가 v번 도시를 통제한다고 정의한다.

i번 도시의 관리 구역은, i번 도시가 통제하는 모든 도시의 집합으로 정의된다.

이에 따라, 1번 도시의 관리 구역은 모든 도시이며, 1≤ i ≤ N인 모든 i에 대해 i번 도시는 i번 도시의 관리 구역에 속한다.

KOI 나라의 도로망을 1번 도시를 루트로 한 트리 구조로 보았을 때, i번 도시의 관리 구역은 i번 도시의 서브트리와 일치한다.

KOI 나라의 각 도시에서 축제를 열려고 한다.

평소에는 모든 도로의 통행료가 무료이지만, 축제가 열릴 때에는 축제를 여는 비용을 충당하기 위해 일부 도로에서 통행료를 걷으려고 한다.

i번 도시에서 축제가 열린다면, 도로 중 일부를 선택하여 통행료를 걷을 수 있다.

일일 통행료 수익은 통행료를 걷는 도로들의 일일 이용량의 합이다.

단, 사람들의 불만을 줄이기 위해 선택하는 도로들은 다음 두 조건을 만족해야 한다:

1≤i ≤ N인 모든 i에 대해, i번 도시에서 축제가 열린다고 가정할 때 일일 통행료 수익의 최댓값을 구하는 프로그램을 작성하라.

축제 timer 1.5s memory 1024MB

축제 1.5s 1024MB