#F6. 皇宫守卫
皇宫守卫
T2 皇宫守卫(guard)
时间限制:1.0 秒 空间限制:256 MB
题目描述
皇宫可以看作一棵有 个房间的树,房间编号为 ,房间之间共有 条走廊。为了保护皇宫,国王决定在一些房间里安排守卫。
在第 个房间安排一名守卫需要花费 的代价。一名守卫可以保护他所在的房间,以及所有与这个房间直接相连的房间。一个房间可以安排多名守卫,但显然不会更优。
请你求出保护所有房间所需的最小总代价。
输入格式
第一行一个正整数 。
第二行 个正整数 。
接下来 行,每行两个正整数 ,表示房间 和房间 之间有一条走廊。
输出格式
输出一行一个整数,表示最小总代价。
样例 1
输入:
3
5 1 5
1 2
2 3
输出:
1
样例 1 解释: 只在 号房间安排一名守卫,他可以保护 号房间,总代价为 。
样例 2
输入:
4
10 1 1 1
1 2
1 3
1 4
输出:
3
样例 2 解释: 在 号房间各安排一名守卫,总代价为 ;若只在 号房间安排守卫则需要代价 ,因此最优答案为 。
数据范围
对于全部测试数据:;;保证输入给出的是一个 个点的树。
子任务
| 子任务 | 分值 | 特殊限制 |
|---|---|---|
| 1 | 20 | |
| 2 | 树是一条链 | |
| 3 | 树是一个菊花( 号点与其余所有点相邻) | |
| 4 | 40 | 无特殊限制 |
提示: 答案可能超过 ,请使用 位整数。