\(\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;

}

巴特西

HDU 6326 Problem H Monster Hunter

\(\mathtt{Problem H}\) \(\mathtt{Monster}\) \(\mathtt{Hunter}\)

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章