Тема: Постройка цикла Гамильтона на дереве.
Дано дерево с 3<=N<=100000 вершинами.Какое минимальное количество рёбер нужно построить чтобы получился цикл Гамильтона?
Re: Постройка цикла Гамильтона на дереве.
идея: запускаем обход в глубину, и просчитываем f[x] - если поддерево с корнем в вершине x превратить в гамильтоновый цикл, то сколько ребер понадобится. Ну и просчитывается она как сумма всех f[его потомков] + <количество потомков> - 2 (что-то наверное типа такого, надо больше примеров рассмотреть, видней будет). Ну и изначально стиреть вершины у которых степень вершины равна двум (это можно прям в двс обрабатывать), это тип если мы вошли в такую вершину, то точно знаем куда выйдем.
Re: Постройка цикла Гамильтона на дереве.
У меня была идея убить вершину с самой большой степенью.А потом из каждой компоненты связности пускать дфс и делать из неё цепь.Потом добавить к ответу кол-во самих компонент(тоесть рёбра, которые нужно будет построить чтобы соединить сами полученые цепи).Как оказалось-идея или реализация была не правильной.
Re: Постройка цикла Гамильтона на дереве.
а можно ссыль на задачку, попробуемс)
Re: Постройка цикла Гамильтона на дереве.
Была такая задача на каком-то контесте. Правильная идея - что ответ равен минимальному количеству путей, которыми можно покрыть это дерево. Решается динамикой по дереву за O(N).