[USACO10HOL] Cow Politics G

农夫约翰的奶牛住在 $n$ 片不同的草地上，标号为 $1$ 到 $n$。 恰好有 $n-1$ 条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点 $p_i$（$0 \le p_i \le n$）。根节点的 $p_i = 0$，表示它没有父节点。 因为奶牛建立了 $1$ 到 $k$ 一共 $k$ 个政党。每只奶牛都要加入某一个政党，其中，第 $i$ 只奶牛属于第 $a_i$（$1 \le a_i \le k$）个政党。而且每个政党至少有两只奶牛。每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。 数据范围：$2 \le n \le 200000$，$1 \le k \le \dfrac n2$

Farmer John's cows are living on N (2 <= N <= 200,000) different pastures conveniently numbered 1..N. Exactly N-1 bidirectional cow paths (of unit length) connect these pastures in various ways, and each pasture is reachable from any other cow pasture by traversing one or more of these paths (thus, the pastures and paths form a graph called a tree). The input for a particular set of pastures will specify the parent node P\_i (0 <= P\_i <= N) for each pasture. The root node will specify parent P\_i == 0, which means it has no parent. The cows have organized K (1 <= K <= N/2) different political parties conveniently numbered 1..K. Each cow identifies with a single political party; cow i identifies with political party A\_i (1 <= A\_i <= K). Each political party includes at least two cows. The political parties are feuding and would like to know how much 'range' each party covers. The range of a party is the largest distance between any two cows within that party (over cow paths). For example, suppose political party 1 consists of cows 1, 3, and 6, political party 2 consists of cows 2, 4, and 5, and the pastures are connected as follows (party 1 members are marked as -n-): -3- | -1- / | \ 2 4 5 | -6- The greatest distance between any two pastures of political party 1 is 3 (between cows 3 and 6), and the greatest distance for political party 2 is 2 (between cows 2 and 4, between cows 4 and 5, and between cows 5 and 2). Help the cows determine party ranges. TIME LIMIT: 2 seconds MEMORY LIMIT: 64MB 农夫约翰的奶牛住在N (2 <= N <= 200,000)片不同的草地上，标号为1到N。恰好有N-1条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点P\_i (0 <= P\_i <= N)。根节点的P\_i == 0, 表示它没有父节点。因为奶牛建立了1到K一共K (1 <= K <= N/2)个政党。每只奶牛都要加入某一个政党，其中， 第i只奶牛属于第A\_i (1 <= A\_i <= K)个政党。而且每个政党至少有两只奶牛。 这些政党互相吵闹争。每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。

\* Line 1: Two space-separated integers: N and K \* Lines 2..N+1: Line i+1 contains two space-separated integers: A\_i and P\_i

\* Lines 1..K: Line i contains a single integer that is the range of party i.

6 2 
1 3 
2 1 
1 0 
2 1 
2 1 
1 5 

3 
2