P2016 Strategic Game

Bob likes playing computer games, especially strategy games. But he often cannot find a quick way to play through a game. Now he has a problem.

He wants to build an ancient castle, where the roads inside form an unrooted tree. He wants to place the minimum number of soldiers on the tree’s nodes so that these soldiers can watch all the roads. Note that when a soldier is on a node, all edges incident to that node can be watched. Please write a program that, given a tree, helps Bob compute the minimum number of soldiers he needs to place.

The first line contains an integer $n$, the number of nodes in the tree. From the second line to the $(n+1)$-th line, each line describes one node’s information in the following order: an integer $i$, the label of this node; a natural number $k$, meaning there are $k$ undirected edges incident to node $i$; followed by $k$ integers, which are the labels of the other endpoints $r_1, r_2, \cdots, r_k$, indicating that there is one undirected edge between $i$ and each of these nodes. For a tree with $n$ nodes, the node labels are between $0$ and $n-1$. In the input, each edge appears exactly once. It is guaranteed that the input describes a tree.

Output a single integer, the minimum number of soldiers required.

Constraints For all test points, $1 \leq n \leq 1500$. Translated by ChatGPT 5