TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2548
  • 题目
  • P2548颜色间距
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    给你一棵由N个节点构成的树。节点编号1到N。树中的N-1条边长度都为1。

    树中的节点都有颜色,一共有M种不同颜色的节点。每种颜色的节点至少有两个。颜色编号1到M。

    现在请你计算,每种颜色的节点中,距离最远的一对节点的距离。
    如下图所示,节点旁边的数字表示颜色。1号颜色最远两个节点是3和6。

    输入格式

    第一行,两个整数N和M
    接下来N行,第i行描述第i号节点,每行两个整数Ci和Fi,分别表示i号节点的颜色和i号节点的父亲节点编号。

    输出格式

    M行,每行一个整数,其中第i行表示涂i号颜色的节点中,距离最远一对节点的距离

    样例输入 1

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

    样例输出 1



    样例输入 2

    15 4
    2 0
    1 1
    3 1
    4 2
    4 2
    2 3
    3 3
    2 4
    3 4
    3 5
    4 5
    1 6
    2 6
    2 7
    1 7

    样例输出 2

    4
    6
    5
    3

    提示

    对于30%的数据 2 <= N <= 1,000
    对于100%的数据 2 <= N <= 200,000
    1 <= M <= N/2


    来源  USACO Andre Kessler 2009