186
правок
Изменения
→Реализация
max_subtree = -1
'''for''' u : children(v)
'''if''' sz[u] > sz[v] / 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) Шаблон решения произвольной задачи на статическую центроидную декомпозицию: <tex>\mathtt{solve}</tex>('''int[]''' children[n], '''int''' v, '''int''' sz[n]) c = <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz) <font color=green>// находим c - центроид поддерева вершины v </font > ch = children[c] <tex>\mathtt{deleteEdges}</tex>(c, children) <font color=green>// удаляем все ребра из вершины с в детей, чтобы мы не смогли из детей попасть в с. Это полезно делать, если решение подзадачи для поддерева предполагает проход dfs </font > '''for''' c2 : ch[c] <tex>\mathtt{solve}</tex>(children, c2, sz) <tex>\mathtt{solveForSubtree}</tex>(children, c2) <font color=green>// решаем для текущего поддерева </font >
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
