113
правок
Изменения
Нет описания правки
== Задача о сумме длин всех путей в дереве ==
Теперь подсчитаем пути для каждого варианта. Обозначим <tex> S[v]\ - </tex> размер поддерева <tex> v </tex>, <tex> F[v]\ - </tex> сумма длин всех путей вершины <tex> v </tex>, <tex> G[v]\ - </tex> количество путей оканчивающихся вершиной <tex> v </tex>, <tex> H[v]\ - </tex> количество путей проходящих через вершину <tex> v </tex>. Если вершина <tex> u </tex> лист, то <tex> S[u] </tex> = 1, а <tex> G[u] </tex> = 0.
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>. Рассмотрим двух сыновей этой вершины: <tex> x </tex> и <tex> y </tex>. Нам надо подсчитать все пути, которые поднимаются из поддерева <tex> x </tex> в <tex> v </tex> и затем опускаются в поддерево <tex> y </tex> и наоборот. То есть по каждому пути, оканчивающимся в вершине <tex> x </tex> мы пройдем столько раз сколько элементов в поддереве <tex> y </tex>, следовательно таких путей будет <tex> G[x]S[y] </tex>. Аналогично, если будем подниматься из поддерева <tex> y </tex>. Также надо учитывать сколько раз мы проходим по ребрам, соединяющим вершины <tex> x </tex> <tex> v </tex> и <tex> y </tex> <tex> x </tex>. Итого для двух вершин <tex> x </tex> и <tex> y </tex>: <tex> G[x]S[y] + G[y]S[x] + 2S[x]S[y] </tex>, следовательно ( <tex> x,y \in Ch(v)</tex>) </tex><tex> H[v] = \sum_{x,y\ x \ne y} \limits{(G[x]S[y] + G[y]S[x] + 2S[x]S[y])} </tex>. Но такой подсчет испортит асимптотику до <tex> O(n^2) </tex>.
Заметим, что <tex> \sum_{x,y} \limits {(G[x]S[y])} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} </tex>. Но еще надо учесть, что <tex> x \ne y </tex>, следовательно <tex> \sum_{x,y\ x \ne y} \limits{(G[x]S[y])} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {(G[x]S[x])} </tex>. Аналогично для <tex> S[x]S[y] </tex>. Итак: <tex> H[v] = 2(\sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {(G[x]S[x])} ) +
2(\sum_{x} \limits {S[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {(S[x]S[x])})</tex>.
Ответ задачи: <tex> F[v] = \sum_{x \in Ch(v)} \limits F[x] + G[v] + H[v] </tex>. Асимптотика каждого слагаемого равна <tex>O \left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left ( n \right )</tex>, где n — количество вершин в дереве, следовательно и <tex> F[v] </tex> находится за <tex> O(n) </tex>.
