Тема: Ещё задача на дереве
Дано неориентированное дерево (2*10^5 вершин) и число k. Мы можем заразить вершину и вместе с ней автоматически заразятся все вершины, удалённые от неё не более чем на k ребер. Нужно за минимальное число заражений заразить всё дерево.
Я пытался делать что-то типа динамики по поддеревьям: хранится информация, насколько удалёна последняя заражённая вершина от корня рассматриваемого поддерева и сколько в поддереве заражённых вершин. На основе этого мы обновляем эти значения для текущей вершины.
Но чувствую,что это лажа), проходит тестов 10.
Задача D отсюда http://neerc.ifmo.ru/school/io/archive/ … vidual.pdf
Бредокод здесь http://ideone.com/FuPnO