题目内容

消防员正在给城市铺设消防栓，城市的道路可以看作一个连通且无回路的图，每条道路有两个底座，消防栓必须铺设在底座上，每条道路必须有消防栓盖；交叉路口只有一个消防栓底座；交叉路口的消防栓可以覆盖连接的所有道路，求至少需要多少个消防栓才能覆盖城市所有的道路?

输入描述

每个 $case$ ，第一行一个整数 $n$ ，表示底座数。($1<=n<=1500$)

题目描述

消防员需要在城市中铺设消防栓。城市的道路可以看作是一棵连通且无回路的树，每个节点代表一个底座，边代表道路。

1.消防栓必须安装在底座上 => 消防栓只能放置在树的节点上

2.每条道路必须有消防栓盖 => 任何一条边都需要满足：所连接的两个节点至少有一个节点上有消防栓。

3.交叉路口只有一个消防栓底座，可以覆盖所有连接的道路 =》 每个节点最多放置一个消防栓，放置了就可以覆盖所有其他节点。