Cow at Large
提交数: 11, 通过率: 18.18%, 平均分: 33.73
题目描述:
贝茜终于被逼到一个偏僻的农场去了。农场由N个谷仓(2≤N≤7*10^4)和N-1条之间的双向隧道谷仓,这样每一对谷
仓间有且仅有一条路径。每个度为1的谷仓是出口。当早晨来临的时候，贝西会在一些谷仓前露面，并试图走到出
口。但是，当贝茜在某个谷仓出现的时候，就有法则能确定她的位置。一些农民会从不同的出口谷仓开始，试图抓
住贝茜。农民们的行动速度和贝茜的速度一样(所以在每一步中，每个农民都可以从一个谷仓转移到另一个相邻的
谷仓)。农民们任何时候都知道贝茜在哪里，贝茜也知道农民们在什么地方。农民们抓住贝茜当且仅当有一个农夫
和贝茜在同一个谷仓里，或者和贝茜穿过同样的隧道。相反，如果贝茜在任何农民抓到她之前，她就能跑到出口谷
仓，她就会逃跑。贝茜不确定她该在哪个谷仓露面（出发）。请帮助贝茜确定如果她出现在每个位置所需要的最少
农民数量，假设农民行走的策略最优。
输入格式:
第一行包含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时间限制: 1000ms
空间限制: 128MB
来源: Usaco2018 Jan Platinum