关于政党的近10条评论(全部评论)
温馨提示：深搜会爆栈 @@@ 2018-07-01 17:41 15楼
就是求一下树的直径么 hyghb 2018-02-25 10:57 14楼
普及一下那个神犇的算法，树上启发式合并dsu on tree http://codeforces.com/blog/entry/44351 FoolMike 2017-08-26 10:38 13楼
蜜汁尴尬，内存开炸= =倍增压tarijin2333 Troywar 2017-07-14 21:44 12楼
第一遍写的时候竟然lca写错了没1A。。。惨啊身败名裂 sxysxy 2016-11-06 10:26 11楼
神TM BFS树剖慢的要死 YGOI_真神名曰驴蛋蛋 2016-09-08 15:46 10楼
感谢楼上神犇教我一个牛犇的定理！！ _Itachi 2016-06-16 21:37 9楼
死活超时过不去两个点 _Itachi 2016-06-16 21:37 8楼
‎MistyEye 2016-06-16 21:27 7楼
遥想当年，我还不会开手工栈，真是naive…… 一個人的雨 2016-04-19 16:24 6楼

803. [USACO Hol10] 政党

★★★ 输入文件：cowpol.in 输出文件：cowpol.out 简单对比
时间限制：2 s 内存限制：128 MiB

农夫约翰的奶牛住在N (2 <= N <= 200,000)片不同的草地上，标号为1到N。恰好有N-1条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。

输入包含一个详细的草地的集合，详细说明了每个草地的父节点P_i (0 <= Pi <= N)。根节点的Pi == 0, 表示它没有父节点。

因为奶牛建立了1到K一共K (1 <= K <= N/2)个政党。每只奶牛都要加入某一个政党，其中，第i只奶牛属于第A_i (1 <= Ai <= K)个政党。而且每个政党至少有两只奶牛。

这些政党互相吵闹争。每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。

比如说，记为政党1包含奶牛1，3和6，政党2包含奶牛2，4和5。这些草地的连接方式如下图所示（政党1由-n-表示）：

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

政党1最大的两只奶牛的距离是3（也就是奶牛3和奶牛6的距离）。政党2最大的两只奶牛的距离是2（也就是奶牛2和4，4和5，还有5和2之间的距离）。

帮助奶牛们求出每个政党的范围。

第一行: 两个由空格隔开的整数: N 和 K

第2到第N+1行: 第i+1行包含两个由空格隔开的整数: Ai和Pi

第1到第K行: 第i行包含一个单独的整数，表示第i个政党的范围。

3
2