Удалите узел в дереве, чтобы ни одно из оставшихся деревьев в лесу не содержало более половины узлов.

Question

Давайте подумаем о дереве (ациклическом связном графе), где у нас есть N вершин и N-1 ребер.Как мы можем определить, существует ли такой узел, что удаление его из дерева приведет к тому, что оставшиеся деревья в лесу будут иметь узлы не более чем в половине всех узлов.И если такой существует, как мы можем узнать, какой это?

Answer 1

Я полагаю, что это может быть достигнуто путем обхода графа, начиная с листьев и подсчета поддеревьев каждого - если это завершено, не достигнув N/2, поэтому вы нашли свой узел.

Рассмотримследующий псевдокод.

set v.count = 0 for all nodes
nodes = all leafs in graph
while true:
    nextStep = new set
    for each v in nodes:
        if v.count < N/2:
            parent = v.parent
            parent.count += v.count + 1 // add another child 
            nextStep.push(parent) // notice that if he exist the new one override
    if nextStep empty:
        break  
    nodes = nextStep // updating with the new set

После завершения этого обхода на всем узле (DFS или что-либо еще) - если у вас все еще был непосещенный узел (как v.count == 0), то нет такогоузел существует, чтобы сломать дерево в соответствии с запросом.если все посещенные узлы, выберите тот, у которого наибольшее количество, и удаление его достигнет вашей цели.

Надеюсь, что поможет!