Chasing a butterfly#11058

Chasing a butterfly (Editorial)

Perform a depth-first search starting from vertex $1$ . For each vertex, compute two values:

$d [v]$ — the distance from vertex $1$ to vertex $v$ . If $p$ is the parent of $v$ , then
$d [v] = d [p] + 1$
d[v] = d[p] + 1
$h [v]$ — the distance from vertex v to the nearest leaf in the subtree rooted at $v$ . If $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k are the children of vertex $v$ , then
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])
If $v$ is a leaf of the tree, set $h [v] = 0$ h[v] = 0.

Next, perform a second depth-first search. During this traversal, compute the value $r es [v]$ — the minimum number of friends that need to be placed in some of the leaves of the subtree rooted at vertex $v$ in order to guarantee catching the butterfly, assuming it chooses to fly into this subtree.

If $h [v] \leq d [v]$ h[v] \le d[v], then $r es [v] = 1$ res[v] = 1. In this case, it is enough to place one friend in the leaf with the minimal depth in the subtree rooted at vertex $v$ : they will reach vertex $v$ no later than the butterfly flying from the root.

Otherwise, if $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k are the children of vertex $v$ , then

r es [v] = r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[v] = res[to_1] + res[to_2] + ... + res[to_k]

If the butterfly is not caught at vertex $v$ itself, we must be prepared to intercept it in any of the subtrees of $v$ 's children.

The final answer to the problem is the value $r es [1]$ .

Example

In the first example (shown in the left diagram), two friends are required, and they should be placed at the two exits. The butterfly can fly from vertex $1$ either to vertex $2$ or to vertex $3$ . In either case, it will be intercepted by one of Nyusha's friends.

In the second example (shown in the right diagram), one friend is enough, who can be placed at either of the two exits — vertex $3$ or $4$ . The butterfly will fly from vertex $1$ to vertex $2$ in one minute. During that same time, the friend will reach vertex $2$ and catch the butterfly there.

Let us consider the next example.

Nyusha will need three friends to catch the butterfly.

Algorithm implementation

Declare a constant for infinity and arrays.

#define INF 2000000000
vector<vector<int> > g;
vector<int> d, h, res;

The function dfs $(v, p, c n t)$ (v, p, cnt) performs a depth-first search starting from vertex $v$ and returns the value $h [v]$ . Here, $p$ is the parent of vertex $v$ , and cnt is the distance from vertex $1$ to $v$ . During the traversal, the values $d [v]$ and $h [v]$ are computed for each vertex $v$ .

int dfs(int v, int p = -1, int cnt = 0)
{

The value $c n t$ , which equals the distance from vertex $1$ to $v$ , is stored in $d [v]$ .

  d[v] = cnt;
  int height = INF;

Iterate over all the children of the vertex $v$ . Consider the edge $v \to t o$ v \to to. If $t o$ equals the parent of $v (t o = p)$ v~(to = p), skip it and move to the next child.

  for (int to : g[v])
    if (to != p)

In the variable $h e i g h t$ compute the value

min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}]),

min(h[to_1], h[to_2], ..., h[to_k]),

where $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k are the children of vertex $v$ .

h e i g h t = min (h e i g h t, df s (t o, v, c n t + 1));

height = min(height, dfs(to, v, cnt + 1));

If $h e i g h t = I N F$ height = INF, then vertex $v$ is a leaf, and set $h [v] = 0$ h[v] = 0. Otherwise rerturn

h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])

h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])

  return h[v] = (height == INF) ? 0 : 1 + height;
}

The function dfs2 $(v, p)$ performs a depth-first search starting from vertex $v$ and returns the value $r es [v]$ . Here, $p$ is the parent of vertex $v$ .

int dfs2(int v, int p = -1)
{
  int s = 0;

Let $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k be the children of vertex $v$ . In the variable $s$ , compute the sum:

r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[to_1] + res[to_2] + ... + res[to_k]

  for (int to : g[v])
    if (to != p)
    {
      dfs2(to, v);
      s += res[to];
    }

If $h [v] \leq d [v]$ h[v] \le d[v], then one friend is sufficient, and $r es [v] = 1$ res[v] = 1. Otherwise

r es [v] = r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}] = s

res[v] = res[to_1] + res[to_2] + ... + res[to_k] = s

  return res[v] = (h[v] <= d[v]) ? 1 : s;
}

The main part of the program. Read the input data. Construct a graph.

scanf("%d", &n);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

C++

Initialize the arrays.

d.resize(n + 1);
h.resize(n + 1);
res.resize(n + 1);

Run two depth-first searches. The first traversal computes the values of $d [v]$ and $h [v]$ for each vertex $v$ .

dfs(1);
dfs2(1);

Print the answer — the minimum number of friends needed to catch the butterfly.

printf("%lld\n", res[1]);