Привет, Codeforces!

Недавно, готовясь к лекции о ДП на поддеревьях, я подумал про обобщение одной из базовых задач на ориентированные ациклические графы. В самом деле, ДП на деревьях и на DAG часто похожи, но в этом случае я не смог быстро придумать не квадратичное решение. И спустя пару дней тоже.

Задача следующая:

В ориентированном графе в каждой вершине $$$u$$$ записано целое число $$$a_u$$$. Для каждой вершины $$$u$$$ требуется найти сумму всех $$$a_v$$$ таких, что $$$v$$$ достижима из $$$u$$$.

После конденсации графа происходит переход к DAG и... Всё. Дальше я вижу только решение за $$$O\left(\frac{N^2}{64} + M\right)$$$ с помощью bitset. Интересно, что постановка задачи очень проста, и кажется, что это должно быть что-то очень известное, но я сталкиваюсь с задачей впервые. Теперь хотелось бы понять, можем ли мы избавиться от $$$N^2$$$ в асимптотике.

Не так давно мне попалась задача B с отбора на олимпиаду Высшая проба по информатике, 10 класс:

Дан массив натуральных чисел $$$a$$$ длины $$$n$$$ и $$$q$$$ запросов, $$$j$$$-й из которых содержит натуральное число $$$x_j$$$. Для $$$j$$$-го запроса требуется определить наибольшее число равных элементов в массиве $$$b$$$, полученном из $$$a$$$ следующим образом: $$$b_i=\lfloor\frac{a_i}{x_j}\rfloor$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$.

В оригинальной задаче ограничения следующие: $$$1 \leq n, q, a_i, x_j \leq 3\cdot10^5$$$. В таком случае я увидел следующее решение:

Но изначально условие попало ко мне в искаженном виде. А именно, ограничения были немного изменены: элементы массива и числа в запросах могли достигать стандартной отметки в $$$10^9$$$. Кажется, задача становится менее тривиальной при таких данных. За какое время её можно решать?