Добрый день!
Как решать такую задачу Сумма ? Я думал как-то при помощи DSU, но не придумал как пересчитывать сумму при объединении множеств.
P.S. 472D - Уроки дизайна задач: обратные задачи в этой задаче сказано, что посчитать расстояния между всеми парами вершин в дереве это очень просто. Можете рассказать как? Дейкстра(и другие аналоги) же от каждой вершины по времени не зайдет
Каждое ребро нужно посчитать столько раз, на скольких путях оно лежит. Дальше понятно?)
Для каждого ребра посчитаем количество путей проходящих через это ребро. Оно равно произведению количества вершин по разные стороны от этого ребра. Т.е. ответ сумма длин ребер на количество путей проходящих через него.
А как быстро считать кол-во вершин по разные стороны ребра? Там
2<=n<=10^5, поэтому надо на каждое ребро тратить не более log(n)Для вершины с "нижней" стороны ребра посчитать k — число вершин в её поддереве. Тогда Число вершин с другой стороны равно n - k.
так это же по времени не пройдет.
Для каждого ребра DFS будет работать за О(k). Всего ребер n — 1, итого суммарное время будет O(n*k), где k будет порядка O(n). За квадрат на таких (
n<=10^5) ограничениях не пройдет. Или я неправильно оценил k?дп по дереву нужно написать. тогда sz найдешь для всех за O(n)
Надо dfs-ом посчитать размеры поддеревьев, и тогда если по одну сторону ребра sz[v] вершин, то по другую (n — sz[v]) вершин.
/blog/entry/17634#comment-224884 , чтобы не повторять
ну пожалуйста
Рекомендую также решить такую смежную задачу:
Дано дерево, для каждой вершины определить сумму длин путей, выходящих из неё.
Задача
Спасибо, сейчас подумаю