Найти ребро максимального веса между двумя узлами в неориентированном ациклическом графе

Question

У нас есть график с N узлами и N-1 двунаправленными ребрами (каждый ребро имеет некоторый вес w ).Теперь мы должны ответить на q количество запросов.Каждый запрос дает два узла u и v и максимально допустимую стоимость на любом ребре x .Если отдельные веса ребер всех ребер между траекториями от u до v меньше или равны x , то мы печатаем Да в противном случае мы печатаем Нет .

Ограничения следующие:
1 ≤ N, q ≤ 10 ^ 6
1 ≤ w, x ≤ 10 ^ 9

Я пробовал решение грубой силы, но оно дает TLE.Я знаю, что мне нужно сделать некоторую предварительную обработку, но я не могу понять это.Я нашел подобный вопрос здесь, но никто не обратил внимание на эту часть.
Максимальный вес ребра от одного узла A до узла B .
Вы можете перейти по ссылке для лучшего объяснения проблемы.

Answer 1

Это может быть легко решено с помощью Union Find (также известной как Diesjoint Set Union, если вы никогда не слышали об этом, вы можете посмотреть реализацию here ) структуры данных в O (n log (n) + q log (q))

1. Прочитать все запросы и сохранить их в некоторой структуре массива (с сохранением информации о запросе u v x и индекса запроса)

2. Сортировка всех запросов по весу

3. Сортировка всех ребер по весу

4. Выполните все запросы, при необходимости объедините все еще неотделенные ребра с весом <= вес запроса </p>

5. Если узлы u и v находятся в одном и том же связанном компоненте (Find (u) == Find (v)), тогда ответ на этот запрос - Да, иначе нет

6. Печать ответов в необходимом порядке