P2971 [USACO10HOL] Cow Politics G

Farmer John's cows live on $n$ different pastures, numbered $1 \sim n$. There are exactly $n-1$ undirected roads of unit length connecting these pastures, and from any pasture you can reach all others. In other words, the pastures and roads form a tree. The input specifies, for each pasture $i$, its parent $p_i$. The root has $p_i = 0$, meaning it has no parent. There are $k$ political parties numbered $1 \sim k$. Each cow joins exactly one party; specifically, cow $i$ (at pasture $i$) belongs to party $a_i$. Each party has at least two cows. Every party wants to know its "range", defined as the distance (along the undirected roads) between the farthest pair of cows within that party.

The first line contains two integers $n, k$. Lines $2 \sim n+1$: line $i+1$ contains two integers $a_i, p_i$.

Output $k$ lines. The $i$-th line contains a single integer, the range of party $i$.

Constraints: $2 \le n \le 2 \times 10^5, 1 \le k \le \frac n2, 0 \le p_i \le n, 1 \le a_i \le k$. Translated by ChatGPT 5