Блог пользователя Fynn

Автор Fynn, 14 лет назад, По-русски
 Мог бы кто-нибудь помочь с этой задачей?
Дано дерево c N (N <= 100 000) вершинами и N - 1 ребром.У каждого ребра есть вес.Нужно от каждой вершины найти путь умножая на вес. Далее прибавляем к ответу.После продолжаем так для всех вершин.
Пример
4
1 2 3
2 3 4
1 4 2
Ответ 51 так как вначале 1-2 придет с 3 далее 1-3 придет 3 * 4 после 1-4 2 после от 2-1 мы не считаем так как мы ее посчитали 2-3 4, 2-4 3 * 2,после от 3-1 и 3-2 не считаем,3-4 4 * 3 * 2,от 4 вершины мы были везде поэтому ее не считаем в итоге получилось 3 + 3 * 4 + 2 + 4 + 3 * 2 + 4 * 3 * 2 = 51.

Ссылка на задачу : http://www.spoj.pl/problems/MTREE/

Если у вас есть время могли бы вы написать разбор по подробнее. Заранее благодарен!!!
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Можно решить линейной динамикой по дереву. Берем первую вершину и подвешиваем дерево за нее. Теперь напишем функцию Solve, которая будет принимать вершину U и возвращать два значения:

1. Сумму весов всех путей, которые начинаются в вершине U и идут куда-то вниз.
2. Сумму весов всех остальных путей в поддереве, корнем которого является вершина U.

Ясно, что ответ на вопрос задачи это суммы этих двух значений при вызове Solve(1).

Чтобы найти эти два значения мы будем перебирать всех сыновей вершины U и вызывать рекурсивно функцию Solve и обрабатывать ее результат определенным образом. Каким именно образом станет понятно, когда вы распишите формулы получения обоих значений для корня из таких же значений для его детей. Например, первое число равно сумме (A+1)*w по всем детям. A - это первое число ребенка, а w - вес ребра от U к этому ребенку. Второе число расписывается похожим образом, но там возникает двойная сумма. Естественно считать ее двойным циклом нельзя, но это не особо сложно обойти, считая все одним циклом и постепенно накапливая нужный результат.