Migrations

문제

The Natural History Museum is investigating the migration patterns of dinosaurs in Bolivia. Paleontologists have discovered dinosaur footprints at $NN$ different sites, numbered from $00$ to $N-1N\; -\; 1$ in order of decreasing age: site $00$ contains the oldest footprints, while site $N-1N\; -\; 1$ holds the youngest.

The dinosaurs migrated to each site (except site $00$) from a specific, older site. For every site $ii$ such that $1\le i\le N-11\; \backslash leq\; i\; \backslash leq\; N\; -\; 1$, there exists exactly one older site $P[i]P[i]$ (with ) such that some dinosaurs migrated directly from site $P[i]P[i]$ to site $ii$. A single older site may have been the source of migrations to multiple younger sites.

The paleontologists model each migration as an undirected connection between sites $ii$ and $P[i]P[i]$. Note that for any two distinct sites $xx$ and $yy$, it is possible to travel from $xx$ to $yy$ by traversing a sequence of connections. The distance between sites $xx$ and $yy$ is defined as the minimum number of connections required to travel from $xx$ to $yy$.

For example, the following image displays a case with $N=5N\; =\; 5$ sites, where $P[1]=0P[1]\; =\; 0$, $P[2]=1P[2]\; =\; 1$, $P[3]=2P[3]\; =\; 2$, and $P[4]=2P[4]\; =\; 2$. One can travel from site $33$ to site $44$ through $22$ connections, so the distance between them is $22$.

The Museum aims to identify a pair of sites with the maximum possible distance.

Note that the pair is not necessarily unique: for instance, in the example above, both pairs $(0,3)(0,\; 3)$ and $(0,4)(0,\; 4)$ have a distance of $33$, which is the maximum. In such cases, any of the pairs attaining the maximum distance is considered valid.

Initially, the values of $P[i]P[i]$ are not known. The Museum sends a research team to visit the sites $1,2,\dots ,N-11,\; 2,\; \backslash ldots,\; N-1$, in order. Upon reaching each site $ii$ ($1\le i\le N-11\; \backslash leq\; i\; \backslash leq\; N-1$), the team performs both of the following actions:

• Determines the value of $P[i]P[i]$, that is, the source of migration to site $ii$.
• Decides whether to send one message to the Museum or not to send any message from this site, based on the previously gathered information.

Messages are transmitted via an expensive satellite communication system, so each message must be an integer between $11$ and $2000020\backslash ,000$, inclusive. Additionally, the team is allowed to send at most $5050$ messages in total.

Your task is to implement a strategy, through which:

• The research team selects the sites from which messages are sent, along with the value of each message.
• The Museum can determine a pair of sites with the maximum distance, based solely on the messages received from each site, knowing from which sites these messages were sent.

Sending large numbers through the satellite is costly. Your score will depend on both the highest integer sent and the total number of messages transmitted.