113
правок
Изменения
Нет описания правки
Теперь оценим количество операций, необходимых нам для нахождения <tex>c[root]</tex>. Так как <tex>c[i]=\max \left ( a[i],b[i] \right )</tex>, то для вычисления <tex>c[root]</tex> необходимо вычислить <tex>a[root]</tex>, <tex>b[root]</tex>. Для вычисления и того, и другого необходимо время порядка <tex>O \left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left ( n \right )</tex>, где <tex> n </tex> — количество число вершин в дереве.
=== Псевдокод ===
'''function''' dfs(x: '''int''', a: '''int''', b: '''int''', c: '''int'''): <font color = darkgreen>//в основной процедуре вызываем dfs от корня(root), после этого ответ будет хранится в c[root] </font color = darkgreen>
'''for''' (i : Ch[x])
dfs(i)
# Пути проходящие через вершину <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> H[v] = \sum_{x,y\ x \ne y} \limits{\Bigl(G[x]S[y] + G[y]S[x] + 2S[x]S[y]\Bigl)} </tex>. Но такой подсчет испортит асимптотику до <tex> O(n^2) </tex>. Заметим, что <tex> \sum_{x,y} \limits {\Bigl(G[x]S[y]\Bigl)} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} </tex>. Но еще надо учесть, что <tex> x \ne y </tex>, следовательно <tex> \sum_{x,y\ x \ne y} \limits{\Bigl(G[x]S[y]\Bigl)} = \sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(G[x]S[x]\Bigl)} </tex>. Аналогично для <tex> S[x]S[y] </tex>. Итак: <tex> H[v] = 2\biggl(\sum_{x} \limits {G[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(G[x]S[x]\Bigl)} \biggl) + 2\biggl(\sum_{x} \limits {S[x]} \sum_{y} \limits {S[y]} - \sum_{x} \limits {\Bigl(S[x]S[x]\Bigl)} \biggl) </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>, где <tex> n </tex> — количество число вершин в дереве, следовательно и время работы самого алгоритма <tex> O \left (n \right ) </tex>.
== Амортизированные оценки для ДП на дереве ==
