10422. Мутуб (Серебро)

В свободное время фермер Джон создал новую службу обмена видео, которую назвал MooTube. На MooTube коровы фермера Джона могут записывать, публиковать и открывать для себя множество забавных видео. Его коровы уже разместили n видео с последовательными номерами 1 ... n. Однако ФД не совсем понимает, как помочь своим коровам найти новые видео, которые им могут понравиться.

ФД хочет создать список "рекомендуемых видео" для каждого видео на MooTube. Таким образом, коровам будут рекомендованы видео, наиболее подходящие тем, которые они уже смотрят.

ФД разрабатывает метрику “релевантности”, которая определяет насколько два видео соответствуют друг другу. Он выбирает n – 1 пар видео и вручную вычисляет их попарное соответствие. Затем ФД визуализирует свои видео как сеть, где каждое видео является узлом, а n – 1 пар видео, которые он вручную рассматривал, связаны. Для удобства ФД выбрал свои n – 1 пар так, чтобы любое видео могло быть доступно из любого другого видео на пути соединений точно одним способом. ФД решает, что релевантность любой пары видео должна определяться как минимальная релевантность любого соединения на этом пути.

Фермер Джон хочет выбрать значение k так, чтобы рядом с любым заданным видео на MooTube предлагались все другие видео, имеющие релевантность как минимум k к этому видео. Однако ФД обеспокоен тем, что его коровам будет предложено слишком много видео, что может отвлечь их от производства молока! Поэтому он хочет тщательно установить соответствующее значение k. Фермеру Джону нужна ваша помощь, чтобы ответить на ряд вопросов о предлагаемых видео для определенных значений k.

Вход. Первая строка содержит числа n (1 ≤ n ≤ 5000) и q (1 ≤ q ≤ 5000). Следующие n – 1 строк описывают пару видеороликов, которые ФД сравнивает вручную. Каждая строка содержит три целых числа p_i, q_i и r_i (1 ≤ p_i, q_i ≤ n, 1 ≤ r_i ≤ 10⁹), что указывает на то, что видео p_i и q_i связаны с релевантностью r_i.

Следующие q строк описывают q запросов фермера Джона. Каждая строка содержит два целых числа k_i и v_i (1 ≤ k_i ≤ 10⁹, 1 ≤ v_i ≤ n) – это означает что в i-ом запросе ФД спрашивает, сколько видеороликов предложит зрителям видео v_i, если k = k_i .

Выход. Выведите q строк. В строке i выведите ответ на i - ый вопрос ФД.

Пример входа

Пример выхода

4 3

1 2 3

2 3 2

2 4 4

1 2

4 1

3 1

РЕШЕНИЕ

поиск в ширину

Анализ алгоритма

Для каждого запроса – пары (k_i, v_i) запустим поиск в глубину или в ширину из вершины v_i. При этом двигаться в поиске будем только по ребрам, вес которых не меньше k_i. Подсчитываем количество посещенных вершин res, не считая стартовую вершину v_i. Значение res и будет ответом на запрос (k_i, v_i).

Пример

Фермер Джон обнаруживает, что видео один и два имеют релевантность 3, видео два и три имеют релевантность 2, а видео два и четыре имеют релевантность 4. Исходя из этого, первое и третье видео имеют релевантность min(3, 2) = 2, первое и четвертое видео имеют релевантность min(3, 4) = 3, а видео три и четыре имеют релевантность min(2, 4) = 2.

Фермер Джон хочет знать, сколько видеороликов будет предложено из второго видео, если k = 1, из первого видео, если k = 3, и из первого видео, если k = 4. Мы видим, что при k = 1 видео 1, 3 и 4 будут предлагаться из второго видео. Если k = 4, то из первого видео не будет предлагаться ничего. Однако при k = 3 видео 2 и 4 будут предлагаться из первого видео.

Реализация алгоритма – поиск в ширину

Входной граф храним в списке смежности g.

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

Функция bfs реализует поиск в ширину из вершины start и возвращает количество посещенных вершин, не считая начальную вершину start. В процессе поиска мы перемещаемся только по тем ребрам, вес которых не меньше k.

int bfs(int start, int k)

{

Массив кратчайших расстояний нам не нужен. Достаточен факт посещения или непосещения вершины. Если вершина i будет посещена, то установим used[i] = 1.

vector<int> used(n + 1);

used[start] = 1;

Объявляем и инициализируем очередь стартовой вершиной start.

queue<int> q;

q.push(start);

Количество посещенных вершин при поиске в ширину (не считая начальную вершину start) подсчитываем в переменной res.

int res = 0;

Запускаем поиск в ширину.

while (!q.empty())

{

Извлекаем вершину v из очереди q.

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

Перебираем ребра, смежные с вершиной v.

for (auto edge : g[v])

{

Рассматриваем ребро (v, to) весом kto.

int to = edge.first;

int kto = edge.second;

Если вес ребра kto меньше k, то такое ребро не рассматриваем (по нему двигаться запрещено).

if (kto < k) continue;

Если вершина to еще не посещена, то заносим ее в очередь, отмечаем пройденной, и увеличиваем количество посещенных вершин res на 1.

if (used[to] == 0)

{

q.push(to);

used[to] = 1;

res++;

}

Возвращаем ответ на запрос.

return res;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &n, &qu);

g.resize(n + 1);

for (i = 0; i < n - 1; i++)

{

scanf("%d %d %d", &p, &q, &r);

Заносим в список смежности неориентированное ребро (p, q) весом r.

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

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

}

Последовательно обрабатываем qu запросов.

while (qu--)

{

scanf("%d %d", &k, &v);

Запускаем поиск в ширину из вершины v. Выводим количество вершин, посещенных в результате поиска в ширину.

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

}

Реализация алгоритма – поиск в глубину

Входной граф храним в списке смежности g.

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

Функция dfs выполняет поиск в глубину из вершины v и возвращает количество посещенных вершин. В процессе поиска мы перемещаемся только по тем ребрам, вес которых не меньше k.

int dfs(int v, int k)

{

Отмечаем посещение вершины v.

used[v] = 1;

В переменной res подсчитываем количество посещенных вершин в поддереве с корнем v в процессе поиска в глубину.

int res = 1;