Luogu P1084 [NOIP2012] 疫情控制

qwq

我们要封锁到根节点所有路径,就需要所有军队往根节点跳,这个过程可以用树上倍增优化。

显然,军队越靠近根,能控制的路径就越多,所以要在有限时间内尽可能往上跳。

答案显然具有单调性(时间越长军队能走的距离越多),可以二分时间。考虑 check 函数。

首先基于上面那条,所有军队尽可能往上跳,如果跳不到根节点,就驻扎。如果能跳到根节点,就有另一种可能性了:可能这支军队需要跨过根节点去另一棵子树驻扎。所以把能到根节点的军队存起来先不驻扎,按到根节点的距离排序。

在根节点的每个子树再 dfs,找出还需要被驻扎的子树。同时之前存下的工具人也需要被再处理:如果一支军队所在的子树需要被驻扎,而且它到了根节点就回不来了,那么就把它直接驻扎。

把处理过的真-工具人根据到了根节点还能走的长度排序,把需要被驻扎的子树根据到根节点的距离排序。有一条显然的贪心,就是小的与小的匹配是最优的。所以拿两个指针扫一遍就做完了。

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
#include <bits/stdc++.h>

typedef long long LL;
const int N = 500000 + 233;
int n, m, army[N], fa[N][20], deg[N];
bool safe[N], need[N];
LL dis[N][20], send[N], receive[N];
std::vector<std::pair<int, int>> g[N];

inline int read() {
int a = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a;
}

void dfs1(int x, int f, LL d) {
fa[x][0] = f, dis[x][0] = d;
for (int i = 1; i <= 18; ++i)
fa[x][i] = fa[fa[x][i - 1]][i - 1],
dis[x][i] = dis[x][i - 1] + dis[fa[x][i - 1]][i - 1];
for (auto t : g[x]) {
int y = t.first, w = t.second;
if (y == f) continue;
dfs1(y, x, w);
}
}

bool dfs2(int x, int f) {
if (safe[x]) return true;
for (auto t : g[x]) {
int y = t.first, w = t.second;
if (y == f) continue;
if (!dfs2(y, x)) return false;
}
return deg[x] == 1 ? false : true;
}

bool check(LL tim) {
int tot = 0;
std::pair<LL, int> free[N];
for (int i = 1; i <= n; ++i) safe[i] = need[i] = false;
send[0] = receive[0] = 0;
for (int i = 1; i <= m; ++i) {
int pos = army[i];
LL cost = 0;
for (int k = 18; k >= 0; --k) {
if (fa[pos][k] > 1 && cost + dis[pos][k] <= tim) {
cost += dis[pos][k];
pos = fa[pos][k];
}
}
if (fa[pos][0] == 1 && dis[pos][0] + cost <= tim) {
free[++tot] = {tim - dis[pos][0] - cost, pos};
} else {
safe[pos] = true;
}
}
for (auto t : g[1])
if (!dfs2(t.first, 1)) need[t.first] = true;
std::sort(free + 1, free + tot + 1);
for (int i = 1; i <= tot; ++i) {
if (need[free[i].second] && free[i].first < dis[free[i].second][0])
need[free[i].second] = false;
else
send[++send[0]] = free[i].first;
}
for (auto t : g[1])
if (need[t.first]) receive[++receive[0]] = dis[t.first][0];
if (send[0] < receive[0]) return false;
std::sort(send + 1, send + 1 + send[0]);
std::sort(receive + 1, receive + 1 + receive[0]);
int pl = 1, pr = 1;
while (pl <= send[0] && pr <= receive[0]) {
if (send[pl] >= receive[pr])
++pl, ++pr;
else
++pl;
}
return pr > receive[0];
}

signed main() {
n = read();
LL l = 1, r = 0, mid, ans = -1;
for (int i = 1; i <= n - 1; ++i) {
int x = read(), y = read(), z = read();
g[x].push_back({y, z}), g[y].push_back({x, z});
++deg[x], ++deg[y];
r += z;
}
m = read();
for (int i = 1; i <= m; ++i) army[i] = read();
dfs1(1, 0, 0);
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid))
r = mid - 1, ans = mid;
else
l = mid + 1;
}
return !printf("%lld\n", ans);
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×