\(\mathtt{Problem H}\) \(\mathtt{Monster}\) \(\mathtt{Hunter}\)
\(\mathcal{Description}\)
给定一棵 \(n\)\((n \leq 10^6)\) 个点的树，除 \(1\) 号结点外每个结点都有一只怪兽，打败他需要先消耗 \(a_i\) 点 \(HP\)，击败后可以获得 \(b_i\) 点 \(HP\)，求打败所有怪兽需要的最小 \(HP\)。
\(\mathcal{Solution}\)
先不考虑父亲的限制关系，考虑最优攻击顺序。
- 对于 \(a_i < b_i\) \(a_j < b_j\) 的怪兽，那 \(a\) 小的优先。
- 对于 \(a_i \geq b_i\) \(a_j < b_j\) 的怪兽，那优先 \(a < b\) 的。
- 对于 \(a_i > b_i\) \(a_j > b_j\) 的怪兽，那 \(b\) 大的优先。
然后再来考虑父亲的限制，对于每个儿子，如果他的优先级大于他的父亲的优先级，那我们可以把他并到他的父亲节点上,假设下次的优先级最高的是兼并后的父节点，相当于先干掉了优先级更高的子节点而后干掉父节点。
\(\mathcal{Code}\)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Node {
long long a, b;
int id;
bool operator <(const Node &x) const {
if (b > a && x.b > x.a)
return a > x.a;
if (b <= a && x.b > x.a)
return true;
if (b <= a && x.b <= x.a)
return x.b > b;
if (b >= a && x.b <= x.a)
return false;
}
} a[N];
priority_queue<Node> q;
vector <int> edge[N];
int fa1[N], fa[N], n;
inline int read() {
int x = 0, k = 1; char c = getchar();
for (; c < 48 || c > 57; c = getchar()) k ^= (c == '-');
for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);
return k ? x : -x;
}
inline long long read1() {
long long x = 0, k = 1; char c = getchar();
for (; c < 48 || c > 57; c = getchar()) k ^= (c == '-');
for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);
return k ? x : -x;
}
void dfs(int x, int fa) {
fa1[x] = fa;
int sz = edge[x].size();
for (int i = 0; i < sz; i++) {
int y = edge[x][i];
if (y == fa)
continue;
dfs(y, x);
}
}
int find(int x) {
return (fa[x] == x) ? x : (fa[x] = find(fa[x]));
}
inline Node Merge(Node a, Node b) {
return (Node)
{a.a + std::max(0ll, - a.b + b.a),
b.b + std::max(0ll, a.b - b.a)};
}
int main() {
n = read();
for (int i = 1; i <= n; i++)
fa[i] = i;
a[1] = (Node) {0, 0, 1};
for (int i = 2; i <= n; i++)
a[i] = (Node) {read1(), read1(), i};
for (int i = 1; i < n; i++) {
int x = read(), y = read();
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(1, 1);
for (int i = 2; i <= n; i++)
q.push(a[i]);
while (!q.empty()) {
Node t = q.top();
q.pop();
if (t.id == 1) continue; // root
if (a[t.id].a != t.a || a[t.id].b != t.b)
continue; // Merge
int Fa = find(fa1[t.id]);
fa[t.id] = Fa;
// Node &tt = a[Fa];
a[Fa] = Merge(a[Fa], a[t.id]);
a[Fa].id = Fa;
q.push(a[Fa]);
}
printf("%lld\n", a[1].a);
return 0;
}