Сначала давайте решим проблему, используя обычные dfs для каждого запроса.Нам нужен логический массив V длиной 100 (так как значения на каждом узле не могут превышать 100), и когда мы пересекаем каждый узел, если V[a[u]] (где u - текущий узел) равен 0установите его на 1 и увеличьте ответ.
Теперь, чтобы решить аналогичную проблему, такую как поиск минимального ребра между двумя узлами, нам нужно использовать разреженную таблицу , которая также используется для поиска LCA , если вы не знаете, что такое разреженная таблица, я рекомендую вам прочитать об этом здесь https://www.hackerrank.com/topics/lowest-common-ancestor (третья часть).Вкратце, это способ найти LCA в O(log n) с предварительной обработкой O(nlogn).
Если мы берем 2 узла u и v и хотим найти минимальный вес на пути, это эквивалентно нахождению минимального минимального веса от u до LCA(u,v) иминимальный вес от v до LCA(u,v).
Чем это полезно?используя разреженную таблицу, вместо того, чтобы просто сохранять, куда попадает узел, если он совершает скачок высоты h, мы также сохраняем минимальное ребро на пути, тогда мы можем просто ответить на каждый запрос со сложностью O(log n).
То же самое относится к этой проблеме, но вместо сохранения минимального значения у нас есть логический массив, как я объяснил в первом подходе, где значение i-th равно 1, если есть грань веса i, когдамы делаем прыжок с высоты h и 0 в противном случае.Используя этот массив, вы сможете отвечать на каждый запрос.
это решение выполняет 100 * log n операций при ответе на запрос, поскольку мы выполняем итерацию по логическому массиву.