题目描述

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.

题目大意

农夫约翰的奶牛住在 $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$

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

3 
2