Farmer John notices that his cows tend to get into arguments if they are packed
too closely together, so he wants to open a series of new barns to help spread
them out.

Whenever FJ constructs a new barn, he connects it with at most one bidirectional
pathway to an existing barn. In order to make sure his cows are spread
sufficiently far apart, he sometimes wants to determine the distance from a
certain barn to the farthest possible barn reachable from it (the distance
between two barns is the number of paths one must traverse to go from one barn
to the other).

FJ will give a total of \(Q\) (\(1 \leq Q \leq 10^5\)) queries, each either of the
form "build" or "distance". For a build query, FJ builds a barn and links it
with at most one previously built barn. For a distance query, FJ asks you the
distance from a certain barn to the farthest barn reachable from it via a series
of pathways. It is guaranteed that the queried barn has already been built.
Please help FJ answer all of these queries.

Problem credits: Anson Hu

Problem credits: Anson Hu

The first line contains the integer \(Q\). Each of the next \(Q\) lines contains a
query. Each query is of the form "B p" or "Q k", respectively telling you to
build a barn and connect it with barn \(p\), or give the farthest distance, as
defined, from barn \(k\). If \(p = -1\), then the new barn will be connected to no
other barn. Otherwise, \(p\) is the index of a barn that has already been built.
The barn indices start from \(1\), so the first barn built is barn \(1\), the second
is barn \(2\), and so on.

Please write one line of output for each distance query. Note that a barn
which is connected to no other barns has farthest distance \(0\).

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Platinum