j00497. 树的最小支配集 未做

某村落由道路连成一棵树。村长要选一个尽可能小的结点子集 $S$ 安排联络员，使树中每个结点要么自己就是联络员（在 $S$ 中），要么至少有一个邻居在 $S$ 中。请输出 $S$ 的最小大小。

第一行一个整数 $n$；接下来 $n-1$ 行每行 $u,v$。

一行一个整数。

• $1\le n\le 2000$
• $1\le u<v\le n$（保证边集构成以 $1$ 为根的树）