MooTube (Silver)#10422

MooTube (Silver) (Editorial)

For each query given by the pair $(k_{i}, v_{i})$ (k_i, v_i), perform a depth-first or breadth-first search starting from vertex $v_{i}$ v_i. During the traversal, only follow edges whose relevance is at least $k_{i}$ k_i.

Count the number of reachable vertices $r es$ , excluding the starting vertex $v_{i}$ v_i. The value of $r es$ is the answer to the query $(k_{i}, v_{i})$ (k_i, v_i).

Example

Farmer John has established the following connections between videos:

Video $1$ and video $2$ have a relevance of $3$ ,
Video $2$ and video $3$ have a relevance of $2$ ,
Video $2$ and video $4$ have a relevance of $4$ .

Based on this data, we can compute the relevance between other pairs of videos:

Video $1$ and video $3$ : relevance = $min (3, 2) = 2$ min(3, 2) = 2,
Video $1$ and video $4$ : relevance = $min (3, 4) = 3$ min(3, 4) = 3,
Video $3$ and video $4$ : relevance = $min (2, 4) = 2$ min(2, 4) = 2.

Now let’s see which videos will be recommended for the following queries:

From video $2$ with $k = 1$ k = 1, videos $1, 3$ , and $4$ will be recommended.
From video $1$ with $k = 3$ k = 3, videos $2$ and $4$ will be recommended.
From video $1$ with $k = 4$ k = 4, no videos will be recommended.

Algorithm implementation — breadth first search

Store the input graph in an adjacency list $g$ .

vector<vector<pair<int, int>>> g;

The bfs function performs a breadth-first search starting from the vertex $s t a r t$ and returns the number of visited vertices, excluding the vertex $s t a r t$ itself. During the search, we only move along edges whose weight is at least the given value $k$ .

int bfs(int start, int k)
{

The shortest distance array is not needed in this problem — it's sufficient to simply track whether a vertex is visited. If vertex $i$ is visited, set $u se d [i] = 1$ used[i] = 1.

  vector<int> used(n + 1);
  used[start] = 1;

Initialize a queue and add the starting vertex $s t a r t$ to it.

  queue<int> q;
  q.push(start);

The number of visited vertices during the breadth-first search (excluding the starting vertex $s t a r t$ ) is counted in the variable $r es$ .

  int res = 0;

Start the breadth-first search.

  while (!q.empty())
  {

Extract the vertex $v$ from the queue $q$ .

    int v = q.front(); q.pop();

Iterate over all edges adjacent to vertex $v$ .

    for (auto edge : g[v])
    {

Consider the edge $(v, t o)$ (v, to) with weight $k t o$ .

     int to = edge.first;
     int kto = edge.second;

If the edge weight $k t o$ is less than $k$ , skip this edge (moving along it is forbidden).

      if (kto < k) continue;

If the vertex $t o$ is not visited yet, add it to the queue, mark it as visited, and increment the counter $r es$ by $1$ .

      if (used[to] == 0)
      {
        q.push(to);
        used[to] = 1;
        res++;
      }
    }
  }

C++

Return the answer to the query.

  return res;
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Add an undirected edge $(p, q)$ with weight $r$ to the adjacency list.

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Process the $q u$ queries one by one.

while (qu--)
{
  scanf("%d %d", &k, &v);

Perform a breadth-first search (BFS) starting from vertex $v$ and print the number of vertices visited during the BFS.

  printf("%d\n", bfs(v, k));
}

Algorithm implementation — depth first search

Store the input graph in an adjacency list $g$ .

vector<vector<pair<int, int>>> g;

The dfs function performs a depth-first search starting from vertex $v$ and returns the number of visited vertices. During the search, we only traverse edges whose weight is not less than the given value $k$ .

int dfs(int v, int k)
{

Mark vertex $v$ as visited.

  used[v] = 1;

Count the number of vertices visited in the subtree rooted at $v$ during the depth-first search in the variable $r es$ .

  int res = 1;

Iterate over all edges adjacent to vertex $v$ .

  for (auto edge : g[v])
  {

Consider the edge $(v, t o)$ (v, to) with weight $k t o$ .

    int to = edge.first;
    int kto = edge.second;

If the weight $k t o$ is less than $k$ , skip this edge (moving along it is forbidden).

    if (kto < k) continue;

If vertex $t o$ is not visited yet, perform a depth-first search starting from it. The number of vertices visited in the subtree rooted at $t o$ is added to $r es$ .

    if (used[to] == 0)
      res += dfs(to, k);
  }
  return res;
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Add an undirected edge $(p, q)$ with weight $r$ to the adjacency list.

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Process the $q u$ queries one by one.

while (qu--)
{
  scanf("%d %d", &k, &v);

Perform a depth-first search starting from vertex $v$ . Print the number of vertices visited during the depth-first search, excluding the starting vertex $v$ .

  used.assign(n + 1, 0);
  printf("%d\n", dfs(v, k) - 1);
}