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