#PU793. USACO 2018 January Contest, Platinum — Problem 2. Cow at Large

    ID: 1511 传统题 文件IO:atlarge 4000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan18来源:usaco.orgscoring:equal_test_cases树形DP深搜

USACO 2018 January Contest, Platinum — Problem 2. Cow at Large

USACO 2018 January Contest, Platinum — Problem 2. Cow at Large

题目描述

Cornered at last, Bessie has gone to ground in a remote farm. The farm consists of NN barns (2≤N≤7⋅1042 \leq N \leq 7 \cdot 10^4) and N−1N-1 bidirectional tunnels between barns, so that there is a unique path between every pair of barns. Every barn which has only one tunnel is an exit. When morning comes, Bessie will surface at some barn and attempt to reach an exit. But the moment Bessie surfaces at some barn, the law will be able to pinpoint her location. Some farmers will then start at various exit barns, and attempt to catch Bessie. The farmers move at the same speed as Bessie (so in each time step, each farmer can move from one barn to an adjacent barn). The farmers know where Bessie is at all times, and Bessie knows where the farmers are at all times. The farmers catch Bessie if at any instant a farmer is in the same barn as Bessie, or crossing the same tunnel as Bessie. Conversely, Bessie escapes if she reaches an exit barn strictly before any farmers catch her. Bessie is unsure at which barn she should surface. For each of the NN barns, help Bessie determine the minimum number of farmers who would be needed to catch Bessie if she surfaced there, assuming that the farmers distribute themselves optimally among the exit barns.

输入格式

The first line of the input contains NN. Each of the following N−1N-1 lines specify two integers, each in the range 1…N1 \ldots N, describing a tunnel between two barns.

输出格式

Please output NN lines, where the iith line of output tells the minimum number of farmers necessary to catch Bessie if she surfaced at the iith barn.

数据范围

(见题面原文)

样例

样例 1

7
1 2
1 3
3 4
3 5
4 6
5 7
3
1
3
3
3
1
1
Problem credits: Dhruv Rohatgi

提示

C/C++/Pascal, and 8 seconds for Java/Python.