P4183 [USACO18JAN]Cow at Large P

    • 87通过
    • 368提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 分治 概率论,统计 点分治 USACO 2018
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

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

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

    输入

    第一行包含 $N$ 。

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

    输出

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

    Translated by @Planet6174

    题目描述

    Cornered at last, Bessie has gone to ground in a remote farm. The farm consists of $N$ barns ($2 \leq N \leq 7 \cdot 10^4$) and $N-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 $N$ 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.

    Note that the time limit for this problem is slightly larger than the default: 4 seconds for C/C++/Pascal, and 8 seconds for Java/Python.

    输入输出格式

    输入格式:

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

    输出格式:

    Please output $N$ lines, where the $i$th line of output tells the minimum number of farmers necessary to catch Bessie if she surfaced at the $i$th barn.

    输入输出样例

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