Please subscribe to the official Codeforces channel in Telegram via the link ×

Help Needed in a Problem

Revision en1, by todorokishotoua1, 2023-03-21 20:16:18

So I came accross the following problem :

Given a rooted tree, find a minimum dominating set such that no two vertices in the dominating set share an edge and for all the vertices that is not in the set, there exists exactly one vertex in the set which is its neighbor. If such a set does not exists, report -1.

I know there is a dp solution for finding the minimum dominating set of a given tree, but i have no idea as to how to approach this question, especially since my dp on trees is really weak.

Any help as to how to approach the problem will be really appreciated. Thank you.

Dominating Set Definition

Tags trees, dp on tree


  Rev. Lang. By When Δ Comment
en1 English todorokishotoua1 2023-03-21 20:16:18 700 Initial revision (published)