P2018 Message Passing

In the Kingdom of Bashu (Bāshǔ), the social hierarchy is strict: except for the king, everyone has exactly one direct superior, and the king has no superior. If $A$ is the superior of $B$, and $B$ is the superior of $C$, then $A$ is the superior of $C$. It is absolutely impossible to have a relationship where $A$ is the superior of $B$ and $B$ is also the superior of $A$. The initial time is $0$. Your task is to spend $1$ unit of time to tell a message to one person, and then let them spread the message on their own. In any time unit, any person who has already received the message can tell the message to one of their direct superiors or direct subordinates. Now, you want to know: 1. How long will it take for the message to reach everyone in the entire Kingdom of Bashu? 2. Which people can be chosen so that the total time spent during transmission is minimized?

The first line of input contains an integer $N$ ($N \le 1000$), the total number of people in the Kingdom of Bashu. People are numbered from $1$ to $N$, and the king’s number is $1$. Lines $2$ through $N$ (a total of $N-1$ lines) each contain one integer; for each $i$ from $2$ to $N$, line $i$ gives the number of the direct superior of person $i$.

The output contains two lines: - The first line contains one integer, the earliest time when the last person receives the message. - The second line contains several integers, the numbers of all valid choices of the initial person, output in increasing order and separated by single spaces.

Translated by ChatGPT 5