Cornered at last, Bessie has gone to ground in a remote farm. The farm consists
of \(N\) barns (\(2 \leq N \leq 10^5\)) 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, 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 before any farms catch her.

Bessie is unsure about her chances of success, which depends on the number of
farmers that the law is able to deploy. Given that Bessie surfaces at barn \(K\),
help Bessie determine the minimum number of farmers who would be needed to catch
Bessie, assuming that the farmers distribute themselves optimally among the exit
barns.

Problem credits: Dhruv Rohatgi

Problem credits: Dhruv Rohatgi

The first line of the input contains \(N\) and \(K\). 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 the minimum number of farmers needed to ensure catching Bessie.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > January > Gold