카이사 - 생존
시간 제한1초메모리 제한1024 MB
루트 있는 트리에서 모든 순서쌍 (x, y)의 LCA를 구해 N^2개 값을 모아 정렬한 뒤, 홀수 번째 위치와 짝수 번째 위치에 있는 값의 합을 각각 출력한다.
문제
준원이(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 Ancestor)는 u의 조상이면서 동시에 v의 조상인 정점들 가운데 깊이가 가장 깊은(가장 아래에 있는) 정점이다.
예를 들어, 예제 2의 입력에 해당하는 트리에서
- 1번과 5번 정점의 LCA는 12번 정점
- 8번과 11번 정점의 LCA는 3번 정점
- 5번과 7번 정점의 LCA는 9번 정점
- 4번과 12번 정점의 LCA는 12번 정점
- 2번과 2번 정점의 LCA는 2번 정점
이다.