P2971 [USACO10HOL]牛的政治Cow Politics

    • 166通过
    • 333提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2010 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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.

    输入输出样例

    输入样例#1: 复制
    6 2 
    1 3 
    2 1 
    1 0 
    2 1 
    2 1 
    1 5 
    
    输出样例#1: 复制
    3 
    2 
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。