P1084 疫情控制

发表于 | 阅读数

给定一些障碍，用这些障碍来切断根节点到所有叶子节点的路径，可以移动障碍，求总时间最少

二分枚举时间显而易见。

每个军队显然越靠近根结点越优，于是我们倍增的往上跳就可以完成这一步。

然后我们检查一遍那些根结点的子树没有被覆盖。

  • 那些没有覆盖的子树，只能靠多余的节点来帮忙覆盖。
  • 将可以进行这些操作的军队提取出来（倍增的往上跳别用它。）
  • 然后再把需要覆盖的根结点的子树的也提取出来。

贪心去思考这个问题，首先为了保证自己覆盖，我一定选择剩余路程最短来覆盖自己或者自己覆盖。即如果搜到自己的时候发现还没覆盖自己当然优先自己子树。

代码 
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const int N = 5e4 + 10;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

vector<pair<int, int>> g[N];

int f[N][20];
ll d[N][20];
int be[N];
int main()
{
    int n = read();
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read(), w = read();
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int m = read();

    vector<int> z(m);
    for (int i = 0; i < m; i++)
        z[i] = read();
    function<void(int, int)> dfs1 = [&](int x, int fa) {
        for (int i = 1; i <= 16; i++)
        {
            f[x][i] = f[f[x][i - 1]][i - 1];
            d[x][i] = d[x][i - 1] + d[f[x][i - 1]][i - 1];
        }
        for (auto [to, w] : g[x])
        {
            if (to == fa)
                continue;
            f[to][0] = x;
            d[to][0] = w;
            be[to] = x == 1 ? to : be[x];
            dfs1(to, x);
        }
    };

    auto check = [&](ll k) {
        vector<pair<ll, int>> tmp;
        vector<pair<ll, int>> need;
        vector<int> tag(n + 1);
        for (int i : z)
        {
            int u = i;
            ll res = 0;
            for (int j = 16; j >= 0; j--)
            {
                if (res + d[u][j] <= k && f[u][j])
                    res += d[u][j], u = f[u][j];
            }
            if (u == 1)
                tmp.push_back({k - res, be[i]});
            else
                tag[u] = 1;
        }
        function<void(int, int)> dfs2 = [&](int x, int fa) {
            int o = 1;
            int cnt = 0;
            for (auto [to, w] : g[x])
            {
                if (to == fa)
                    continue;
                dfs2(to, x);
                cnt++;
                o &= tag[to];
            }
            if (tag[x] == 0)
            {

                if (!cnt)
                    tag[x] = 0;
                else if (o == 1)
                    tag[x] = 1;
                else
                    tag[x] = 0;
            }
        };
        dfs2(1, 0);
        for (auto [to, w] : g[1])
        {
            if (!tag[to])
                need.push_back({w, to});
        }
        sort(tmp.begin(), tmp.end());
        sort(need.begin(), need.end());
        if (need.size() == 0)
            return 1;
        int j = 0;

        for (auto [dis, i] : tmp)
        {

            if (j >= need.size())
                return 1;
            if (!tag[i])
                tag[i] = 1;
            else if (dis >= need[j].first)
                tag[need[j].second] = 1;
            while (j < need.size() && tag[need[j].second])
                j++;
        }
        if (j >= need.size())
            return 1;
        else
            return 0;
    };
    dfs1(1, 0);
    // cout << check(9) << endl;
    ll l = 0, r = 1e15, ans = -1;
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid - 1;
            ans = mid;
        }
        else
            l = mid + 1;
    }
    cout << ans << endl;
}