Мог бы кто-нибудь помочь с этой задачей?
Дано дерево 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/
Если у вас есть время могли бы вы написать разбор по подробнее. Заранее благодарен!!!
Дано дерево 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/
Если у вас есть время могли бы вы написать разбор по подробнее. Заранее благодарен!!!
