964. Minimum Dominating Set on a Tree

Given a tree with n nodes labeled 0..n-1 (rooted at 0) and an undirected edge list, return the size of the minimum dominating set — the smallest set of nodes such that every node is either in the set or adjacent to a node in the set. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the minimum dominating set size.

Examples

Input: {"n":5,"edges":[[0,1],[0,2],[1,3],[1,4]]}
Output: 2
Explanation: Nodes 0 and 1 dominate the tree.

Input: {"n":1,"edges":[]}
Output: 1
Explanation: The single node must be chosen.

Input: {"n":3,"edges":[[0,1],[0,2]]}
Output: 1
Explanation: The center dominates both leaves.

Constraints

• 1<=n<=10^5
• edges form a tree

Asked by