该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P2971 [USACO10HOL] Cow Politics G

题目描述

农夫约翰的奶牛住在 $n$ 片不同的草地上，标号为 $1\sim n$。

恰好有 $n-1$ 条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点 $p_i$。根节点的 $p_i=0$, 表示它没有父节点。

因为奶牛建立了 $1\sim k$ 一共 $k$ 个政党。每只奶牛都要加入某一个政党，其中， 第 $i$ 只奶牛属于第 $a_i$ 个政党。而且每个政党至少有两只奶牛。 每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。

输入格式

第一行两个整数 $n,k$。

第 $2\sim n+1$ 行：第 $i+1$ 行两个整数 $a_i,p_i$。

输出格式

一共 $K$ 行，第 $i$ 行一个整数表示第 $i$ 个政党的范围。

输入输出样例 #1

输入 #1

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

输出 #1

3 
2

说明/提示

数据范围：$2 \le n \le 2\times10^5,1 \le k \le \frac n2,0\le p_i\le n,1\le a_i\le k$。