当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

7096：Subtraction

题目描述
给定一棵 $n$ 个节点的无根树，节点编号由 $1$ 到 $n$，节点 $i$ 有正整数权值 $b_i$ 和度数限制 $p_i$。你可以进行如下操作若干次：

- 选择这棵树的一个连通块（即选择一个导出子图连通的节点的子集），满足每个在该连通块内的节点 $i$ 在该连通块中的度数不超过 $p_i$。对于属于该连通块的所有节点 $i$，令 $b_i$ 减少 $1$。

求最少的操作次数使得每个节点的 $b_i$ 均变为 $0$。
输入解释
本题有多组测试数据。

第一行一个整数 $T(1 \leq T \leq 10)$ 表示数据组数。

对于每组数据，第一行一个整数 $n(1 \leq n \leq 2 \times 10^5)$ 表示节点数。

接下来 $n-1$ 行每行两个整数 $u, v$ 描述树上的一条边。

接下来 $n$ 行每行两个整数 $b_i, p_i(1 \leq b_i \leq 10^9, 1 \leq p_i \leq n)$ 依次描述每个节点。
输出解释
对于每组数据输出一行一个整数，表示最少的操作次数。
输入样例 
2
3
1 2
1 3
4 1
5 3
1 2
7
1 2
1 3
3 4
3 5
3 6
5 7
2 2
10 3
3 3
2 4
3 1
4 2
1 4
输出样例 
6
13
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2021 年百度之星·程序设计大赛 - 复赛
源链接： HDU-7096
最后修改于 2021-10-23T19:11:25+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
10000/5000MS(Java/Others) 131072/131072K(Java/Others)