Изменения
Исправлена ошибка в реализации
Поиск центроида в дереве:
'''int''' <tex>\mathtt{findCentroid}</tex>('''int[]''' children[n], '''int''' v, '''int[]''' sz, '''int''' tree_size)
max_subtree = -1
'''for''' u : children(v)
'''if''' sz[u] > sz[v] tree_size / 2 '''and''' sz[u] > sz[max_subtree] <font color=green>// считаем sz[-1] = 0 </font >
max_subtree = u
'''if''' max_subtree == -1
return v
'''else'''
'''return''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz, tree_size)
Шаблон решения произвольной задачи на статическую центроидную декомпозицию:
<tex>\mathtt{solve}</tex>('''int[]''' children[n], '''int''' v, '''int[]''' sz)
c = <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz, sz[v]) <font color=green>// находим c {{---}} центроид поддерева вершины v </font >
ch = children[c]
<tex>\mathtt{deleteEdges}</tex>(c, children) <font color=green>// удаляем все ребра между вершиной с и детьми, чтобы мы не смогли из детей попасть в с.
