186
правок
Изменения
→Статическая центроидная декомпозиция
Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.
}}
=== Реализация ===
Поиск центроида в дереве:
'''int''' <tex>\mathtt{find_centroid}</tex>('''int[]''' children[n], '''int''' v, '''int''' sz[n])
max_subtree = -1
'''for''' u : children(v)
'''if''' sz[u] > sz[v] / 2 and sz[u] > sz[max_subtree] // считаем sz[-1] = 0
max_subtree = u
'''if''' max_subtree == -1
return v
'''else'''
return find_centroid(children, max_subtree, sz)
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
