TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4615
  • 题目
  • P4615【USACO 2018 JAN Platinum】抓奶牛
    限制 : 时间限制 : 20000 MS   空间限制 : 265536 KB
    评测说明 : 1s,256m
    问题描述

    贝茜被农民们逼进了一个偏僻的农场。农场可视为一棵有 N个结点的树,结点分别编号为 1,2,…,N。每个叶子结点都是出入口。开始时,每个出入口都可以放一个农民(也可以不放)。每个时刻,贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了(在边上或点上均算),则贝茜将被抓住。抓捕过程中,农民们与贝茜均知道对方在哪个结点。

    请问:对于结点 i(1≤i≤N),如果开始时贝茜在该结点,最少有多少农民,她才会被抓住。

    输入格式

     第一行包含 N。

    在接下来的 N−1行中,每行有两个在 1∼N 范围内的整数,表示一条边。

    输出格式

    输出 N 行,第 i 行表示如果开始时贝茜在结点 i ,最少有多少农民,她才会被抓住。

    样例输入

    7
    1 2
    1 3
    3 4
    3 5
    4 6
    5 7

    样例输出

    3
    1
    3
    3
    3
    1
    1

    提示

    对于100%的数据:2≤N≤7×10^4