DMOPC '14 Contest 5 P6 - Save Nagato!

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.4s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are about to change history!

You have recently been informed of cruel and inhumane tests on Nagato by the classless Am*ricans. Being a responsible citizen, you have decided to take matters into your own hands and stop the imbecile Am*ricans from destroying such a beautiful and majestic ship.

The Un*ted St*tes Armed Forces (made up of those Am*ricans, henceforth known as USAF) has N members and a hierarchy in which every member (except the President) has exactly one direct superior. Each member of the USAF has a rank. The rank of the President is 1, and each other member's rank is the rank of their direct superior plus 1. For example, if someone's direct superior was the President, their rank would be 2. It is guaranteed that if you follow the chain of superiors of any member of the USAF, you will eventually reach the President.

Your master plan is to immerse the President in anime and manga until he realizes the foolishness of his actions and becomes a weeaboo, after which he will immediately cancel the planned destruction of the Nagato.

You have already gathered a lot of information of the USAF, but you cannot execute your plan yet as some crucial pieces of information are missing. Although you know information such as "these two people form an inferior-superior pair" (that is, one of them is the direct superior of the other), you do not know who is the superior and you do not actually know which person in the USAF (numbered from 1 to N) is the President. And most alarmingly, you do not know how many unique ranks there are among members of the USAF (every rank has a specific etiquette guideline you must learn before you can infiltrate the USAF).

Since the President's number is highly classified, you would like to determine the number of unique ranks in the USAF regardless of which of the members 1 to N you assume is the President.


Subtask 1 [20%]

1 \le N \le 500

Subtask 2 [30%]

1 \le N \le 7\,000

Subtask 3 [50%]

1 \le N \le 500\,000

Input Specification

The first line of input will have N.
The next N - 1 lines of input will each contain a superior-inferior pair u\ v (1 \le u, v \le N, u \neq v). It is guaranteed that the information corresponds to a valid hierarchy assuming each of the N members is the President.

Output Specification

You should output N lines. On the i^{th} line, you should output the number of unique ranks assuming that member i is the President.

Sample Input

2 1
2 3

Sample Output


Explanation for Sample Input

The following diagrams shows the hierarchy of the USAF for each of the three cases where person 1, 2, and 3 are the President. The star next to each person shows their rank.

Case 1

There are 3 unique ranks: 1, 2, and 3.

Case 2

There are 2 unique ranks: 1 and 2. Note that both member 1 and member 2 have rank 2, so it's only counted once.

Case 3

There are 3 unique ranks: 1, 2, and 3. Note that this case is symmetrical to the first case.

Everything appearing in this problem is fictitious. Any resemblance to real countries, people, or battleships is purely coincidental. Nagato


  • 3
    madhur4127  commented on June 10, 2020, 8:22 a.m.

    Popular name for this is "tree rerooting" technique. Tutorial

  • 1
    Riolku  commented on Dec. 20, 2018, 5:06 p.m. edited

    Despite rewriting my solution multiple times and using fast input, I am still unable to pass any cases in the last batch. My solution is O(N) as illustrated by the editorial.

    EDIT: I found the reason.

  • -8
    hahahajokes  commented on Nov. 29, 2017, 8:16 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

    • -10
      felixzhang25  commented on Aug. 23, 2018, 9:14 a.m. edited

      This comment is hidden due to too much negative feedback. Click here to view it.