DDOSvoid's Blog

Luogu P1084 疫情控制

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P1084

细节还挺多的一道题

Solution

我们二分答案x，显然的操作是每个点一定往上走

但是我们注意到不能停在根节点，所以有可能有的点要穿过根节点到根节点的另一个儿子的地方

这里也可以贪心处理

有一个细节需要注意，，就是如果u能到根，但u的子树没人覆盖，这时候有可能是另一个v来覆盖u的子树，而u去覆盖别的子树。但这种v的剩余时间一定小于u，所以当遍历到u的时候，发现u的子树没人覆盖，用u覆盖就行

时间复杂度 $O(nlog^2)$

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 50010
#define ll long long
#define cn const node
using namespace std;

int n, m, a[maxn], rt;

struct Edge {
    int to, next, w;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

int f[maxn][21]; ll dis[maxn]; 
void dfs(int u, int fa) { 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w; if (v == fa) continue;
        dis[v] = dis[u] + w; f[v][0] = u;
        dfs(v, u);
    }
}

void init_f() {
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
}

bool vis[maxn]; 
bool Dfs(int u, int fa) {
    bool F = 0, s = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue; 
        F = 1; vis[v] |= vis[u]; s &= Dfs(v, u);
    }
    if (!F) return vis[u];
    return s;
} 

struct node {
    int k; ll v; 

    node() {}
    node(int _k, ll _v) { k = _k; v = _v; }

    friend bool operator < (cn &u, cn &v) { return u.v < v.v; }
} b[maxn], c[maxn]; int c2, c3; 
bool check(ll x) { c2 = c3 = 0; memset(vis, 0, sizeof vis); 
    for (int i = 1; i <= m; ++i) {
        int u = a[i]; ll X = x; 
        for (int j = 20; ~j; --j)
            if (f[u][j] && f[u][j] != rt && dis[u] - dis[f[u][j]] <= X)
                X -= dis[u] - dis[f[u][j]], u = f[u][j]; 
        if (f[u][0] == rt && X > dis[u]) b[++c2] = node(u, X - dis[u]);
        else vis[u] = 1; 
    }
    for (int i = head[rt]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (Dfs(v, rt)) continue;
        c[++c3] = node(v, w);
    }
    sort(b + 1, b + c2 + 1); sort(c + 1, c + c3 + 1); int j = 1;
    for (int i = 1; i <= c3; ++i, ++j) {
        while (j <= c2 && b[j].v < c[i].v && b[j].k != c[i].k) ++j; 
        if (j == c2 + 1) return 0;
    }
    return 1;
} 
    

int main() { memset(head, -1, sizeof head); 
    cin >> n; rt = 1; 
    for (int i = 1; i < n; ++i) {
        int x, y, z; cin >> x >> y >> z;
        add_edge(x, y, z); add_edge(y, x, z);
    } dfs(rt, 0); init_f(); cin >> m;
    for (int i = 1; i <= m; ++i) cin >> a[i];
    ll l = 0, r = 500000000000000ll, mid, ans = -1;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    } cout << ans << endl;
    return 0;
}