题目描述
消防员需要在城市中铺设消防栓。城市的道路可以看作是一棵连通且无回路的树，每个节点代表一个底座，边代表道路。
1.消防栓必须安装在底座上 => 消防栓只能放置在树的节点上
2.每条道路必须有消防栓盖 => 任何一条边都需要满足：所连接的两个节点至少有一个节点上有消防栓。
3.交叉路口只有一个消防栓底座，可以覆盖所有连接的道路 =》 每个节点最多放置一个消防栓，放置了就可以覆盖所有其他节点。
题目内容
某市消防部门需要在道路上布置消防栓。城市道路结构可以看作一个连通且不含环的图。每条道路的两端各设置一个底座；如果多条道路交汇于同一个交叉路口，则这些道路在该路口共用一个公共底座。消防栓只能安装在底座上，并且每条道路都必须获得消防栓盖，即该道路至少需要被一个消防栓覆盖。交叉路口处安装的消防栓可以覆盖所有与该路口相连的道路。
给定整个城市路网的连接关系，请计算最少需要安装多少个消防栓，才能覆盖全部道路。
约束条件
- 底座总数 n 满足 1≤n≤1500。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
