「牛客 CSP-S 模拟赛」躲避技能 - 树上差分 + 贪心 + 高精度

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

牛客链接（需付费）

鸡尾酒是一个多操手，他可以同时操作 \(m\) 个账号。今天，他使用这些账号一起打一个 boss。这个 boss 战的地图共有 \(n\) 个关键点，其中有 \(n - 1\) 条边，每条边连接着两个不同的点，使得从任意点出发可以到达其他所有的点。鸡尾酒的 \(m\) 个账号分别编号 \(1\) 至 \(m\)，一开始，第 \(i\) 个账号在点 \(s_i\)。可能有两个账号在同一位置。

现在，boss 放出了一个致命技能。boss 在地图上标出了 \(m\) 个关键点，想成功躲避这个技能，必须在每一个被标记的点上，都有一个账号站在上面。注意，可能会有点被多次标记，多次标记的点需要有多个账号站在上面。

由于鸡尾酒无法分身，所以 他必须先把一个账号移动到一个位置，才能动另一个账号，不能同时移动多个账号。假设鸡尾酒的任意账号通过第 \(i\) 条边的时间为 \(w_i\)，请帮鸡尾酒求出他成功躲避技能所需要的最少时间。

数据范围：\(1 \le n, m \le 10^5\)，\(1 \le w_i \le 10^{100}\)。

解题思路

通过贪心分析题目性质，我们可以发现对于一颗子树，优先在子树中匹配是不劣的。因为两点仅有一条路径，且匹配到子树外必须经过根的边，于是优先在子树中匹配可尽量少走必须的边。这样我们就可以通过 DFS 得出方案。

考虑树上差分，我们对每个起点标记 \(+1\)，在每个终点标记 \(-1\)，从任一点开始 DFS 进行树上差分即可判断出在何时两点匹配。计算答案时只需将子树的答案加起来再加上未匹配的点经过边到达父亲所需的边权即可。由于 \(w_i\) 过大，此题再写个高精即可。

代码演示

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>

const int MAXN = 1e5;

struct BigInt {
    static const int MAXM = 100;

    std::vector<int> v;

    BigInt(const int n = 0) { *this = n; }

    BigInt &operator=(int x) {
        v.clear();
        do v.push_back(x % 10); while (x /= 10);
        return *this;
    }

    BigInt &read() {
        char s[MAXN + 1];
        scanf("%s", s);
        int len = strlen(s);
        v.resize(len);
        for (size_t i = 0; i < len; i++) v[i] = s[i] - '0';
        return *this;
    }

    void print() {
        for (int i = v.size() - 1; i >= 0; i--) printf("%d", v[i]);
        putchar('\n');
    }
};

BigInt operator+(const BigInt &a, const BigInt &b) {
    BigInt res;
    res.v.clear();
    bool flag = false;
    for (size_t i = 0; i < std::max(a.v.size(), b.v.size()); i++) {
        int t = 0;
        if (i < a.v.size()) t += a.v[i];
        if (i < b.v.size()) t += b.v[i];
        if (flag) t++, flag = false;
        if (t >= 10) t -= 10, flag = true;
        res.v.push_back(t);
    }
    if (flag) res.v.push_back(1);
    return res;
}

BigInt &operator+=(BigInt &a, const BigInt &b) {
    return a = a + b;
}

BigInt operator*(const BigInt &a, const BigInt &b) {
    BigInt res;
    res.v.resize(a.v.size() + b.v.size() + 1);
    for (size_t i = 0; i < a.v.size(); i++) {
        for (size_t j = 0; j < b.v.size(); j++) {
            res.v[i + j] += a.v[i] * b.v[j];
            res.v[i + j + 1] += res.v[i + j] / 10;
            res.v[i + j] %= 10;
        }
    }
    while (res.v.size() > 1 && res.v.back() == 0) res.v.pop_back();
    return res;
}

struct Node {
    std::vector<struct Edge> adj;
    int cnt;
} N[MAXN + 1];

struct Edge {
    Node *s, *t;
    BigInt w;

    Edge(Node *s, Node *t, BigInt w) : s(s), t(t), w(w) {}
};

inline void addEdge(int u, int v, BigInt w) {
    N[u].adj.push_back(Edge(&N[u], &N[v], w));
    N[v].adj.push_back(Edge(&N[v], &N[u], w));
}

std::pair<BigInt, int> dfs(Node *u, Node *fa = nullptr) {
    BigInt val = 0;
    int cnt = u->cnt;

    for (Edge e : u->adj) {
        if (e.t == fa) continue;
        std::pair<BigInt, int> res = dfs(e.t, u);
        res.first += std::abs(res.second) * e.w;
        val += res.first, cnt += res.second;
    }

    return std::make_pair(val, cnt);
}

int main() {
    int n, m;

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int s;
        scanf("%d", &s);
        N[s].cnt++;
    }
    for (int i = 1; i <= m; i++) {
        int t;
        scanf("%d", &t);
        N[t].cnt--;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        BigInt w;
        scanf("%d %d", &u, &v);
        w.read();
        addEdge(u, v, w);
    }

    dfs(&N[1]).first.print();

    return 0;
}