20506번 - Kaisar - 생존

준원이(0/5/3)는 생존해있는 카이사(2/7/0)를 찾으러 소환사의 협곡을 수색하고 있다. 협곡은 정점이 N개 있는 트리 모양이고, 정점은 1번 정점에서 N번 정점까지 번호 붙여져 있다. 준원이는 모든 정점 쌍 x, y에 대해 x번 정점과 y번 정점의 LCA를 방문해보고, 방문한 정점의 번호들을 모두 배열에 적어두었다. 여러 번 방문하면 여러 번 적었다.

하지만, 카이사는 없었다.

준원이는 탈주하고, 이 배열을 정렬한 뒤, 배열의 짝수번째 원소들의 합과 홀수번째 원소들의 합을 구하려 한다.

참가자 - 생존

참가자 - 생존

첫째 줄에는 트리의 정점의 개수 N이 주어진다.

둘째 줄에는, 1번부터 N번까지 각 정점의 부모 정점의 번호를 나타내는 N개의 정수가 차례대로 주어진다. 루트 정점은 부모가 없으므로, 루트 정점의 차례에는 0이 주어진다.

준원이가 정렬한 배열의 짝수번째 원소들의 합과 홀수번째 원소들의 합을 차례대로 공백을 사이에 두고 출력한다. 출력하는 수가 32비트 정수 자료형의 범위를 넘을 수 있다는 점에 유의하라.

• 1 ≤ N ≤ 200,000

트리에서, 두 정점 u, v의 LCA(Lowest Common Ancester)는, u의 조상이기도 하고 v의 조상이기도 한 정점들 가운데 가장 깊이가 깊은(아래에 있는) 정점이다.

예를 들어, 예제 2의 입력에 해당하는 트리에서,

• 1번과 5번 정점의 LCA는 12번 정점
• 8번과 11번 정점의 LCA는 3번 정점
• 5번과 7번 정점의 LCA는 9번 정점
• 4번과 12번 정점의 LCA는 12번 정점
• 2번과 2번 정점의 LCA는 2번 정점

이다.