자전거 대여소 계층 비교

문제

공유 자전거 서비스의 대여소 N곳은 1번 중앙 대여소를 뿌리로 하는 트리 모양으로 관리된다. 2번부터 N번까지의 대여소 i 는 상위 대여소 p_i 를 하나씩 가지며 p_i < i 이다. 각 대여소 i 에는 거치대가 a_i 개 있다. 어떤 대여소 v 가 대여소 u 의 상위 대여소란, v 가 u 의 부모이거나 부모의 부모처럼 위로 거슬러 올라가면 닿는 대여소를 말한다. u 자신은 포함하지 않는다. 운영팀은 거치대 수가 상위 대여소보다 더 많은 '확장형' 관계를 점검하려 한다. 상위 대여소 v 와 그 아래 대여소 u 의 쌍 (v, u) 중 a_v < a_u 를 만족하는 쌍을 '확장 쌍'이라 한다. 거치대 수가 같은 쌍은 확장 쌍이 아니다. 대여소 u 마다 u 의 상위 대여소 중 a_v < a_u 인 것의 수를 c_u 라 하자. 모든 확장 쌍의 수를 구하고, c_u 가 최대인 대여소와 그 최댓값도 구하는 프로그램을 작성하라. 최댓값이 같은 대여소가 여럿이면 번호가 가장 작은 대여소를 고른다. 모든 c_u 가 0 이면 1번 대여소와 0 을 출력한다. 트리가 한 줄처럼 깊어질 수 있으므로 재귀 호출이 너무 깊어지지 않게 주의해야 한다.

입력

첫 줄에 N 이 주어진다. (1 ≤ N ≤ 200,000) 둘째 줄에 p_2 … p_N 이 공백으로 주어진다. (1 ≤ p_i < i) N = 1 이면 이 줄은 비어 있다. 셋째 줄에 a_1 … a_N 이 공백으로 주어진다. (1 ≤ a_i ≤ 10^9, 정수)

출력

한 줄에 확장 쌍의 수, c_u 가 최대인 대여소 번호, 그 최댓값을 공백으로 구분해 출력한다.

5
1 1 2 2
3 5 2 6 1

3 4 2

1

7

0 1 0

4
1 2 3
1 2 2 3

5 4 3

출처: Devin.KR 자체 제작