겹치지 않는 기획전 고르기

문제

온라인 쇼핑몰의 상품 분류는 1번 분류를 뿌리로 하는 트리 구조이다. 2번 이상의 각 분류 i에는 상위 분류 p_i가 정해져 있으며 p_i < i이다. 각 분류 i에는 기획전을 열었을 때 얻는 이익 c_i가 있다. 메인 화면에 기획전을 열 분류를 몇 개 고르려 한다. 단, 어떤 분류와 그 분류의 하위 분류(자식, 손자 등 모든 자손)에서 동시에 기획전을 열 수는 없다. 즉 고른 두 분류 중 한쪽이 다른 쪽의 조상이 되어서는 안 된다. 아무 분류도 고르지 않아도 된다. 고른 분류의 이익 합을 최대로 하는 것이 목표이다. 이익 합이 최대인 방법이 여러 가지라면 고른 분류의 개수가 가장 적은 방법을 택한다. 분류 v의 부분 트리에서 얻을 수 있는 최선은, v 자신만 고르는 경우와 v의 자식들 각각의 부분 트리에서 얻은 최선을 합친 경우 중 더 좋은 쪽이라는 재귀적 구조를 가진다. 최대 이익 합과, 그 이익 합을 내는 방법 중 고른 분류 개수의 최솟값을 구하라.

입력

첫 줄에 분류의 수 N이 주어진다. 둘째 줄에 p_2, p_3, …, p_N이 공백으로 구분되어 주어진다(N = 1이면 빈 줄). 셋째 줄에 c_1, c_2, …, c_N이 주어진다. 모든 값은 정수이며 1 ≤ N ≤ 200000, 1 ≤ p_i < i, 0 ≤ c_i ≤ 10^9이다.

출력

최대 이익 합과 그때 고른 분류 개수의 최솟값을 공백으로 구분해 한 줄에 출력한다.

5
1 1 2 2
5 3 4 2 2

8 3

3
1 1
6 3 3

6 1

1

0

0 0

출처: Devin.KR 자체 제작