Cow Politics

Farmer John's cows live on $N$ pastures ($2 \le N \le 200{,}000$) numbered $1 \dots N$. Exactly $N - 1$ bidirectional paths, each of unit length, connect the pastures so that every pasture is reachable from every other one. The pastures and paths therefore form a tree.

Each pasture $i$ is described by its parent $P_i$ ($0 \le P_i \le N$). The root pasture has parent $P_i = 0$, meaning it has no parent.

The cows have organized $K$ political parties ($1 \le K \le N/2$) numbered $1 \dots K$. Every cow belongs to exactly one party; cow $i$ belongs to party $A_i$ ($1 \le A_i \le K$). Each party contains at least two cows.

The range of a party is the greatest distance between any two cows in that party, where the distance between two cows is the number of paths on the route connecting their pastures.

For example, suppose party 1 consists of cows 1, 3, and 6, party 2 consists of cows 2, 4, and 5, and the pastures are connected as shown below (party 1 members are marked with dashes):

  -3-
   |
  -1-
 / | \
2  4  5
      |
     -6-

The greatest distance between two cows of party 1 is 3 (between cows 3 and 6), and the greatest distance for party 2 is 2 (for instance, between cows 2 and 4). So party 1 has range 3 and party 2 has range 2.

Determine the range of every party.

• Line 1: two space-separated integers $N$ and $K$.
• Lines $2 \dots N+1$: line $i + 1$ contains two space-separated integers $A_i$ and $P_i$, describing pasture $i$.

• Lines $1 \dots K$: line $i$ contains a single integer, the range of party $i$.