Monster Hunter(贪心)

描述

传送门: 2018 Multi-University Training Contest 3 - Problem H

Little Q is fighting against scary monsters in the game “Monster Hunter”. The battlefield consists of $n$ intersections, labeled by $1,2,…,n$, connected by $n-1$ bidirectional roads. Little Q is now at the $1$-th intersection, with $X$ units of health point(HP).
There is a monster at each intersection except $1$. When Little Q moves to the $k$-th intersection, he must battle with the monster at the $k$-th intersection. During the battle, he will lose $a_i$ units of HP. And when he finally beats the monster, he will be awarded $b_i$ units of HP. Note that when HP becomes negative($<0$), the game will over, so never let this happen. There is no need to have a battle at the same intersection twice because monsters do not have extra life.
When all monsters are cleared, Little Q will win the game. Please write a program to compute the minimum initial HP that can lead to victory.

Input

The first line of the input contains an integer $T(1\leq T\leq2000)$, denoting the number of test cases.\par
In each test case, there is one integer $n(2\leq n\leq 100000)$ in the first line, denoting the number of intersections.
For the next $n-1$ lines, each line contains two integers $a_i,b_i(0\leq a_i,b_i\leq 10^9)$, describing monsters at the $2,3,…,n$-th intersection.
For the next $n-1$ lines, each line contains two integers $u$ and $v$, denoting a bidirectional road between the $u$-th intersection and the $v$-th intersection.
It is guaranteed that $\sum n\leq 10^6$.

Output

For each test case, print a single line containing an integer, denoting the minimum initial HP.

Sample Input

1
2
3
4
5
6
7
8
1
4
2 6
5 4
6 2
1 2
2 3
3 4

Sample Output

1
3

思路

  • 在不考虑树的偏序限制的情况下,就是经典的流水线调度贪心。使用Johnson法则排序即可。
  • 考虑原问题,先求出忽略父亲限制的最优攻击顺序:$p_1, p_2, p_3, \ldots, p_n$。
    • 若$p_1$是树根,则第一步打$p_1$一定最优;
    • 否则,在打完$p_1$的父亲$x$之后接着打$p_1$一定最优。
      把$p_1$和$x$两只怪兽合并为一只,并将$p_1$的所有儿子的父亲改为$x$。
  • 这样就可以规模为$n$的问题变成$n - 1$的问题,重复上述操作直到只剩下一个怪兽。
  • 用堆来维护最优怪兽,并查集维护父亲即可。具体实现见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
struct Node
{
ll a, b;
Node(ll a = 0, ll b = 0) : a(a), b(b) {}
bool operator<(const Node& rhs) const
{
int sgn1 = a < b, sgn2 = rhs.a < rhs.b;
return sgn1 < sgn2 || sgn1 == sgn2 && (a < b ? a > rhs.a : b < rhs.b);
}
Node& operator+=(const Node& rhs)
{
Node ret = *this;
ret.a = max(a, a - b + rhs.a);
ret.b = b + rhs.b - a - rhs.a + ret.a;
return *this = ret;
}
};

typedef pair<Node, int> HeapNode;
typedef __gnu_pbds::priority_queue<HeapNode> Heap;

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
vector<Node> a(n + 1);
vector<int> fa(n + 1), del(n + 1);
vector<vector<int> > G(n + 1);

for (int i = 2; i <= n; i++) scanf("%lld%lld", &a[i].a, &a[i].b);
for (int i = 1, u, v; i < n; i++)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}

static function<void(int, int)> dfs = [&](int u, int p) {
fa[u] = p;
for (auto& v : G[u])
if (v != p) dfs(v, u);
};

dfs(1, 0);

static function<int(int)> find = [&](int x) { return del[fa[x]] ? fa[x] = find(fa[x]) : fa[x]; };

Heap q;
vector<Heap::point_iterator> id(n + 1);
for (int i = 2; i <= n; i++) id[i] = q.push({a[i], i});
while (!q.empty())
{
HeapNode t = q.top();
q.pop();
int x = t.second;
del[x] = 1;
int y = find(x);
a[y] += a[x];
if (y > 1)
{
if (id[y] != 0)
q.modify(id[y], {a[y], y});
else
id[y] = q.push({a[y], y});
}
}
printf("%lld\n", a[1].a);
}
return 0;
}
捐助作者
0%