Чехол Vertex для жадного подхода к дереву
Вопрос: Пусть T будет деревом с n узлами, корнем которого является некоторый узел r. Мы хотим разместить как можно меньше защитных элементов в узлах T, так что каждое ребро T охраняется: ребро между родительским узлом v и его дочерним элементом w охраняется, если один из них устанавливает охрану хотя бы на один из этих двух узлов v., ш. Дайте O(n) временной алгоритм для нахождения оптимального решения задачи.
Мой подход состоял в том, чтобы сделать обратный пост-порядок из корня и установить защиту на узел, который является частью неохраняемого ребра, за исключением того, что этот узел является листом... но этот алгоритм не будет работать, если все узлы будут расположены в линейная цепочка, потому что мой алгоритм установит охрану на каждом узле, кроме концов цепочки.
Я посмотрел онлайн и проверил решения DP, которые имеют смысл для меня, но мне было интересно, есть ли жадный алгоритм, чтобы найти покрытие вершины для дерева