Привет, Codeforces!
Недавно, готовясь к лекции о ДП на поддеревьях, я подумал про обобщение одной из базовых задач на ориентированные ациклические графы. В самом деле, ДП на деревьях и на DAG часто похожи, но в этом случае я не смог быстро придумать не квадратичное решение. И спустя пару дней тоже.
Задача следующая:
В ориентированном графе в каждой вершине $$$u$$$ записано целое число $$$a_u$$$. Для каждой вершины $$$u$$$ требуется найти сумму всех $$$a_v$$$ таких, что $$$v$$$ достижима из $$$u$$$.
После конденсации графа происходит переход к DAG и... Всё. Дальше я вижу только решение за $$$O\left(\frac{N^2}{64} + M\right)$$$ с помощью bitset. Интересно, что постановка задачи очень проста, и кажется, что это должно быть что-то очень известное, но я сталкиваюсь с задачей впервые. Теперь хотелось бы понять, можем ли мы избавиться от $$$N^2$$$ в асимптотике.
От $$$N^2$$$ можем избавиться, например, вот так: $$$O\left(\frac{N^2}{64} + M\right) = O\left(\frac{\sqrt{N}^4}{64} + M\right)$$$. Не благодари.
Автокомментарий: текст был обновлен пользователем SleepingCat (предыдущая версия, новая версия, сравнить).
Чуть-чуть поизучал теорию и узнал, что мы такое, кажется, решать не умеем. Это открытая проблема. Более того, я ошибся в подсчете времени работы алгоритма, и моё решение работает за $$$O\left(\frac{N(N + M)}{64}\right)$$$.
Вот немного обсуждений чего-то подобного:
https://mirror.codeforces.com/blog/entry/80649?locale=ru
https://cstheory.stackexchange.com/questions/4258/number-of-reachable-vertices-in-dag-for-every-vertex
https://stackoverflow.com/questions/29871692/finding-reachable-vertices-for-every-vertex-in-a-directed-graph
https://cs.stackexchange.com/questions/142842/given-dag-gv-e-find-forall-v-in-v-the-sum-of-the-weights-of-vertices-th