Kaisa - Survival

Time limit1sMemory limit1024 MB

Summary

Given a rooted tree, take the LCA of every ordered pair of vertices (including x=y), collect all N^2 results into one multiset, sort it, then print the sum of values at odd and even positions.

Level: Hard8 of 10
Topics: Tree, DFS, Math, Combinatorics
Solved: No attempts yet

Problem

Junwon (0/5/3) is searching Summoner's Rift for the surviving Kaisa (2/7/0). The Rift is a tree with N vertices, numbered 1 through N. For every pair of vertices x, y, Junwon visited the LCA of vertex x and vertex y, and wrote down the number of each visited vertex in an array. If he visited a vertex several times, he wrote it down that many times.

But Kaisa was not there.

Junwon leaves the game, and after sorting this array, he wants to find the sum of the elements in even positions and the sum of the elements in odd positions.

Participant - Survival

Input

The first line gives the number of vertices N in the tree.

The second line gives N integers in order, the parent vertex number of each vertex from 1 to N. The root has no parent, so a 0 is given in the root's place.

Output

Print the sum of the elements in even positions and the sum of the elements in odd positions of the array Junwon sorted, in that order, separated by a space. Note that the printed numbers may exceed the range of a 32-bit integer type.

Constraints

1 ≤ N ≤ 200,000

Hint

In a tree, the LCA (Lowest Common Ancestor) of two vertices u and v is the deepest (lowest) vertex among the vertices that are ancestors of both u and v.

For example, in the tree corresponding to the input of sample 2,

the LCA of vertices 1 and 5 is vertex 12
the LCA of vertices 8 and 11 is vertex 3
the LCA of vertices 5 and 7 is vertex 9
the LCA of vertices 4 and 12 is vertex 12
the LCA of vertices 2 and 2 is vertex 2

Examples2

Example 1
Input
```
5
0 1 1 2 2
```
Expected output
```
19 22
```
Example 2
Input
```
12
12 9 2 6 6 12 9 3 0 3 3 9
```
Expected output
```
584 578
```