HDU7096. Subtraction
题意：
给定一棵\(n\)个节点的无根树，节点编号由\(1\)到\(n\)，节点\(i\)有正整数权值\(b_i\)和度数限制\(p_i\)。你可以进行如下操作若干次：
选择这棵树的一个连通块，满足每个在该连通块内的节点\(i\)在该连通块中的度数不超过\(p_i\)。对于属于该连通块的所有节点\(i\)，令\(b_i\)减少\(1\)。
求最少的操作次数使得每个节点的\(b_i\)均变为\(0\)。
分析：
我们尝试随意定义一个节点为根节点，不妨令\(1\)为根节点，那么这棵树的父子关系就确定了。
考虑对于一个根节点，若以其所有子节点为根节点的子树的最优操作方法都已经计算出来，我们能不能通过这些子树的最优操作方法得到整个树的最优操作方法。
先考虑子树最后尝试和父节点合并的情况（即子树内部得到最优解后，再与父节点合并，从直观上来说，这种情况最容易考虑）。假设这个父节点是\(i\)节点，要使得它的\(b_i\)变为\(0\)，就需要操作\(b_i\)次，这\(b_i\)个操作，每个都是最多和\(p_i\)个子树合并，我们希望合并的次数越多越好，故而可以遍历子树的最优操作方法，查看这些操作之中哪些可以与父节点合并，优先和父节点中被合并次数少的操作进行合并，这个贪心很显然是正确的，我们就得到了子树最后和父节点合并的情况的最优解。
再考虑子树先和父节点合并产生最优解的情况，对于这个情况，我可以做到撤消某一个与父节点合并的操作，使得某个子树变得不是最优解，即子树内部至少可以再进行一次合并操作，所以先和子树合并并不会使答案变得更劣。
整体思路如此，细节部分每个人想法不同。
我的做法：考虑开一个re数组，re[i]表示\(i\)节点上有多少操作可以和父节点合并。rem表示当前节点上还能合并多少个操作。合并的时候注意细节。
代码：
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long Lint;
const int maxn = 2e5 + 10;
vector<int> G[maxn];
Lint ans;
Lint b[maxn];
int p[maxn];
Lint re[maxn];
void dfs(int u, int f) {
for (auto v : G[u]) {
if (v == f) continue;
dfs(v, u);
}
Lint rem = b[u] * p[u];
for (auto v : G[u]) {
if (v == f) continue;
// 考虑u和v子节点合并
// 不能超过v的可合并数，不能超过u节点的操作数，也不能超过u节点剩余可合并次数
Lint tmp = min(min(re[v], b[u]), rem);
// 多出来的就算可以合并也没机会再合并了，统计进答案
ans += re[v] - tmp;
rem -= tmp;
}
re[u] = min(b[u], rem);
// 那些没法与父节点合并的操作，统计进答案
ans += b[u] - re[u];
}
int n;
void solve() {
ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
G[i].clear();
}
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
scanf("%lld%d", &b[i], &p[i]);
}
dfs(1, 0);
// 根节点多出来的也没机会合并了，统计进答案
ans += re[1];
printf("%lld\n", ans);
}
int main() {
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}