Problems Base course RU

The farthest page

You can move around a site only by breadcrumbs: from a page up to its section, or down into one of its subsections. Pages and sections form a tree rooted at the home page. For each page, find how many clicks it is from the farthest page of the site.

One of the tests is the real tree of this site’s addresses: 8986 nodes, from the home page down to the pages of worked exam problems.

Input

The first line holds n (1 ≤ n ≤ 100,000); pages are numbered from 1 to n, and the home page is 1. The second holds n − 1 numbers p₂, …, p_n: the section page i belongs to. A section’s number is not necessarily smaller than the page’s number.

Output

n numbers separated by spaces: for each page in order, the number of clicks to the page farthest from it.

Examples

Example 1

Input

7
1 1 2 2 3 6

Output

3 4 3 5 5 4 5

Example 2

Input

5
1 2 3 4

Output

4 3 2 3 4

Limits

Time · Python: 2000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

A breadth-first traversal from each page gives the answer, but that is n traversals of n steps, eighty million already on the site’s tree. Can the answer for a child be obtained from the answer for its parent?

2Hint 2

The longest path from page v either goes down into its section or first climbs to the parent. The first is computed bottom up. What do you need to know about the parent to compute the second?

3Hint 3

Having climbed from c to its parent v, the path may go higher or down into any branch of v except the branch of c itself. So for v you need to remember not one deepest branch but two.

4The idea

Rerooting in two passes. Bottom up, for each page v compute d₁[v] and d₂[v], the depths of its two deepest branches through different children, and remember which child the first goes through. Top down, compute up[c], the longest path from c that starts with a step up: up[c] = 1 + max(up[v], the best branch of v not through c), where the best branch is d₁[v], or d₂[v] if the first goes through c. The answer for a page is max(d₁, up).

5Walkthrough

A breadth-first order from the home page puts parents before children: the bottom-up pass walks it backwards, the top-down pass forwards. Section numbers in the input are not necessarily smaller than page numbers, so the order of numbers cannot be relied on; the order has to be built. There is no recursion, and a chain of a hundred thousand pages holds no fear.

Why two branches are enough: a path from c through the parent cannot return into the branch of c, since the tree has no cycles, and it would pass along the edge c–v twice. So of all the branches of v it can use all but one, and the best of those available is either the deepest or the second deepest.

On this site’s tree the home page’s answer is 6, the number of clicks to the deepest English pages. The deepest pages, worked exam problems, have an answer of 11: the farthest from them are the same worked problems in the other language.

5+Solution

6Complexity

O(n) time and memory: two passes over the list, a constant number of operations per page.

7Common mistakes

A traversal from each page. Correct, but quadratic: it runs out of time already on the site’s tree.
Only one best branch at the parent. If it goes through c itself, the path “up and back down” counts that edge twice, and the answer comes out larger than the real one.
Only downwards. d₁[v] is the answer only for the home page; for the others the farthest page often lies in another section.

Algorithms behind it

DP Technique Dynamic programming on trees A subtree’s answer from its children’s answers: a pass from the leaves to the root, and for all roots at once, rerooting. O(n) 2 problems GRA Algorithm Breadth-first search Walks a graph in layers and finds paths with the fewest edges in O(V + E). O(V + E) 2 problems