Блог пользователя 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
  • Проголосовать: не нравится

Автор Fynn, 14 лет назад, По-русски
1. задача http://algoprog.kz/ej/contests/5/statements/palindromes/ какая тут должна быть динамика?
2. задача http://www.spoj.pl/problems/AIBOHP/

если можете могли бы вы писать подробный разбор

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится