Все упирается в тот факт, что если у вершины нету "пока что плохих" потомков, то в нее надо ставить полк только в том случае, если эта вершина — корень дерева (иначе можно поставить полк в предке этой вершины, он "закроет" ее, и при этом, возможно, еще каких-то "братьев").

Дальше можно все легко свести к одному dfs — обойдем дерево в глубину, и, возвращаясь от листьев в корню, будем поступать так: если вершина сейчас не является листом — ставим полк и отрезаем от дерева все то, что закрыла эта вершина.

Т.е., в плане реализации — будем ставить полки тогда и только тогда, когда потомок еще не "закрыт", или же наша вершина — корень.