113
правок
Изменения
Нет описания правки
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>, где <tex> n </tex> — количество вершин в дереве, следовательно и <tex> F[v] </tex> находится за время работы самого алгоритма <tex> O(n) </tex>.
== Амортизированные оценки для ДП на дереве ==
