Привет, Codeforces!

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

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

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

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