oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

voyage Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

voyage.html

Problem Description

Coco the Monkey lives on an island, numbered 1. An explorer is going on a voyage over N days. On day 1, he stays on the island Coco the Monkey is at. On day 2, he discovers island 2. On day 3, he discovers island 3. On day i, he discovers island i.

For each island that he discovers, he opens up a sea route that connects the newly discovered island to one island that has already been discovered. All sea routes are of equal length. Initially, only the island Coco the Monkey lives on is considered discovered.

On each day, Coco the Monkey wonders, what is the longest distance between two discovered islands? Answer Coco the Monkey's queries!

Input

The first line of input will contain one integer, N.

The next N - 1 lines of input will contain one integer each, the island that the newly discovered island is connected to by a sea route.

Output

Output N - 1 lines. On the ith line, output the longest possible distance between any two discovered islands on day (i+1).

Limits

Subtask 1 (36%): 2 ≤ N ≤ 1000.

Subtask 2 (64%): 2 ≤ N ≤ 200 000.

Subtask 3 (0%): Sample Testcases

Sample Testcase 1

Input

6
1
2
2
1
5

Output

1
2 
2 
3
4

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
136511s64MBMinimum
264511s64MBMinimum
3011s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o voyage -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.