113
правок
Изменения
Нет описания правки
== Задача о сумме длин всех путей в дереве ==
Путь задано подвешенное дерево. Рассмотрим количество путей для вершины <tex> v </tex>. Во-первых, это пути не проходящие через эту вершину, то есть все пути между её сыновьями. Во-вторых, пути, которые оканчиваются вершиной <tex> v </tex>. И в третьих, это пути проходящие через вершину <tex> v </tex>, они начинаются из поддерева одного из сыновей этой вершины и заканчиваются в другом поддереве одного из сыновей вершины <tex> v </tex>.
Теперь подсчитаем пути для каждого варианта. Обозначим <tex> S[v]\ - </tex> размер поддерева <tex> v </tex>, <tex> F[v]\ - </tex> сумма длин всех путей вершины <tex> v </tex>, <tex> G[v]\ - </tex> количество путей оканчивающихся вершиной <tex> v </tex>.
1. Пути не проходящие через эту вершину. Это просто сумма суммы длин для всех поддеревьев детей или <tex> F[v] = \sum_{x \in Ch(v)} \limits F[x]</tex>.
2. Пути оканчивающиеся в вершине <tex> v </tex>. Рассмотрим ребро, соединяющее вершину <tex> v </tex> и одного ее сына, пусть это будет вершина <tex> g </tex>. Переберем все пути, которые начинаются с этого ребра и идут вниз. Это будет сумма путей оканчивающихся в <tex> g + S[g] </tex>, так как суммарная длина поддерева <tex> g </tex> уже сосчитана и каждый такой путь мы продлили ребром, соединяющим вершины <tex> v </tex> и <tex> g </tex>. Всего таких путей: <tex> G[v] = \sum_{x \in Ch(v)} \limits {(G[x] + S[x])}</tex>.
3. Пути проходящие через вершину <tex> v </tex>.
