Форум Всеукраїнської інтернет-олімпіади NetOI

Первое, что приходит в голову - сделать динамику по дереву.

Количество частей в результате разреза дерева равняется числу разрезанных ребер + 1. То есть достаточно построить такой разрез, который минимизирует количество разрываемых ребер, и мы получим ответ к задаче.
Введем функцию f(v,sz), где v-вершина дерева, sz - количество вершин, которые в этом поддереве можно оставить соединенными с v.
тогда все зависит от того, сколько потомков у вершины v:
0. v-лист. Ничего разрезать точно не надо. f(v,sz)=0
1. у v есть 1 потомок. Значит можно либо разрезать ребро к потомку, либо не разрезать. f(v,sz)=min(f(chld[v],sz-1),f(chld[v],k)+1)
2 тут выходит 4 разных варианта.
- удалить оба ребра к детям. если сделать так, то в сумме в поддереве будет сделано f(left[v],k)+f(right[v],k)+2 разрезов.
- удалить только ребро к левому сыну. Тогда будет f(left[v],k)+f(right[v],sz-1)+1
- удалить только ребро к правому сыну. Тогда будет f(right[v],k)+f(left[v],sz-1)+1
- не удалять не одного из ребер. ответом для этого случая будет min(f(left[v],i)+f(right[v],sz-1-i)) по i от 1 до sz-2.
f(v,sz) будет равняться минимуму из этих 4 вариантов.

А имея посчитанную функцию f, восстановить удаленные ребра - это уже дело техники.

Про жадность - согласен. Это первое, что приходит в голову. Но очевидной и при этом правильной жадности я тут не вижу.
А динамика - железный способ.

Ні. Не школярі реєструються у категорії НЕ ШКОЛЯРІ

Усцака

Dark_Dimius написав:

necro написав:

Усцака

не совсем понял, ето выражение эмоций или инет-проект с заданными характеристиками?)))

Насколько я понимаю, имелся в виду Usaco :-)