【NOIP2012】疫情控制

发表于
https://loj.ac/problem/2607

题目链接

【NOIP2012】疫情控制

做法

这道题显然可以二分答案。
考虑构造解。对于每个军队，当它不能到达首都时，它的深度显然越小越好。对于可以到达首都的军队，它有两种决策：退回上一个位置、去填补其他子树的最上面节点。可以用倍增维护。
考虑一种特殊数据：

1
2
3
4
5
6
5
1 2 5
1 3 2
1 4 5
4 5 1000000000
3 3 4 5

它的构造方案是 $ 5 \to 5, 4 \to 3, 3 \to 2 $ ，答案是 $ 7 $ 。
考虑一个能到达根节点的军队（从 $ root $ 的儿子 $ x $ 来），若它的步数还能回到上一个位置（并非时光倒流），则直接将它放在根节点考虑没有影响；否则它要么去一个 $ dis(root, x) \geq dis(root, y), y \in son(root) $ 的地方，要么待在 $ x $ 。这部分可以用 $ multiset $ 维护。
最后贪心地从首都分配军队。 

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
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int N = 300010;
int n, m, cnt[N],fa[19][N], fr[N], flag[N]; ll ans = -1;
struct P {
	int to; ll w; P(int To = 0, ll W = 0) : to(To), w(W) {}
	inline bool operator<(const P &yy)const { return w > yy.w; }
}; vector<P> e[N];
ll depw[N];
ll a[N], b[N]; int la, lb;
vector<ll> hv[N];
multiset<ll> st;

template<typename T> inline void gi(T &x) {
	x = 0; register char c = getchar(), pre = 0;
	for(; c < '0' || c > '9'; pre = c, c = getchar());
	for(; c >= '0' && c <= '9'; c = getchar()) x = 10ll * x + (c ^ 48);
	if(pre == '-') x = -x;
}
void dfs(int u, int ff, int anc) {
	if(ff == 1) anc = u; fr[u] = anc, fa[0][u] = ff;
	rep(i, 1, 18) fa[i][u] = fa[i - 1][fa[i - 1][u]];
	for(auto v : e[u]) if(v.to != ff) depw[v.to] = depw[u] + v.w, dfs(v.to, u, anc);
}
void solve(int u, int ff) {
	if(flag[u] || e[u].size() == 1) return ;
	int cnt = 0, now = 0;
	for(auto v : e[u]) if(v.to != ff) ++cnt, solve(v.to, u), now += flag[v.to];
	if(cnt == now) flag[u] = 1;
}
bool check(ll x) {
	la = lb = 0; rep(i, 1, n) flag[i] = 0, hv[i].clear(); st.clear();
	if(cnt[1]) { rep(i, 1, cnt[1]) a[++la] = x; }
	rep(i, 2, n) if(cnt[i]) {
		if(depw[i] <= x)
			rep(j, 1, cnt[i]) {
				if(depw[fr[i]] <= x - depw[i]) a[++la] = x - depw[i];
				else hv[fr[i]].pb(x - depw[i]);
			}
		else {
			int anc = i; ll tmp = x;
			per(j, 18, 0)
				if(fa[j][anc] && depw[anc] - depw[fa[j][anc]] <= tmp)
					tmp -= depw[anc] - depw[fa[j][anc]], anc = fa[j][anc];
			flag[anc] = 1;
		}
	}
	for(auto v : e[1]) {
		solve(v.to, 1), sort(hv[v.to].begin(), hv[v.to].end(), greater<ll>());
		if(!flag[v.to]) {
			multiset<ll>::iterator it = st.lower_bound(v.w);
			if(it != st.end() && (!hv[v.to].size() || *it <= hv[v.to].back()))
				st.erase(it), flag[v.to] = 1;
			else if(hv[v.to].size()) hv[v.to].pop_back(), flag[v.to] = 1;
		}
		for(auto i : hv[v.to]) st.insert(i); if(!flag[v.to]) b[++lb] = v.w;
	}
	sort(a + 1, a + la + 1), sort(b + 1, b + lb + 1);
	int p1 = 1, p2 = 1;
	for(; p1 <= la && p2 <= lb; ++p1, ++p2) {
		for(; p1 <= la && a[p1] < b[p2]; ++p1);
		if(p1 > la) break;
	}
	return p2 > lb;
}
int main() {
	gi(n);
	rep(i, 2, n) { int x, y, z; gi(x), gi(y), gi(z), e[x].pb(P(y, z)), e[y].pb(P(x, z)); }
	sort(e[1].begin(), e[1].end());
	gi(m); rep(i, 1, m) { int x; gi(x), ++cnt[x]; }
	dfs(1, 0, 0);
	ll l = 0, r = 1e16, mid;
	for(; l <= r;) mid = (l + r) / 2, check(mid) ? (ans = mid, r = mid - 1) : l = mid + 1;
	printf("%lld\n", ans);
	return 0;
}