疫情控制

推荐博客

二分+倍增+贪心选择。

考虑在有限时间内将所有的军队调到能达到的最靠近根节点的点，并记录还有多余时间的军队。

选择剩余时间更多的去别的路径，而剩余时间小的留在当前路径。（口胡

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAXN = 50005;
const int MAXL = 55;
struct edge {
	int v, w;
	edge() {}
	edge(int V, int W) {
		v = V;
		w = W;
	}
};
vector<edge> mp[MAXN];
int query[MAXN], n, m, Max;

inline void Add_Edge(int u, int v, int w) {
	mp[u].push_back(edge(v, w));
	mp[v].push_back(edge(u, w));
}

int fa[MAXN][MAXL];
LL dist[MAXN][MAXL], dep[MAXN];
void init() {
	queue<int> q;
	q.push(1);
	dep[1] = 1;
	while(!q.empty()) {
		int t = q.front();
		q.pop(); 
		for(int i = 0; i < mp[t].size(); i++) {
			int v = mp[t][i].v;
			int cost = mp[t][i].w;
			if(dep[v])
				continue;
			dep[v] = dep[t] + 1;
			fa[v][0] = t;
			dist[v][0] = cost;
			for(int j = 1; j <= Max; j++) {
				fa[v][j] = fa[fa[v][j - 1]][j - 1];
				dist[v][j] = dist[v][j - 1] + dist[fa[v][j - 1]][j - 1];
			}
			q.push(v);
		}
	}
}

struct data {
	int t, index;
	data() {}
	data(int T, int Index) {
		t = T;
		index = Index;
	}
};
data Free[MAXN];
LL tim[MAXN], ned[MAXN];
int len = 0, len2 = 0, len3 = 0;
bool vis[MAXN], need[MAXN];

bool find(int x) {
	if(vis[x])
		return true;
	bool flag = false;
	for(int i = 0; i < mp[x].size(); i++) {
		int v = mp[x][i].v;
		if(dep[v] < dep[x])
			continue;
		flag = true;
		if(!find(v))
			return false;
	}
	if(!flag)
		return false;
	return true;
}

bool cmp(data x, data y) {
	return x.t > y.t;
}

bool check(LL flag) {
	memset(need, 0, sizeof need);
	memset(vis, 0, sizeof vis);
	memset(tim, 0, sizeof tim);
	memset(ned, 0, sizeof ned);
	for(int i = 1; i <= len; i++) 
		Free[i] = data(0, 0);
	len = 0, len2 = 0, len3 = 0;
	for(int i = 1; i <= m; i++) {
		int x = query[i];
		LL tot = 0;
		for(int j = Max; j >= 0; j--)
			if(fa[x][j] > 1 && tot + dist[x][j] <= flag) {
				tot += dist[x][j];
				x = fa[x][j];
			}
		if(fa[x][0] == 1 && tot + dist[x][0] <= flag) 
			Free[++len] = data(flag - tot - dist[x][0], x);			
		else
			vis[x] = true;
	}
	
	for(int i = 0; i < mp[1].size(); i++) {
		int v = mp[1][i].v;
		if(!find(v))
			need[v] = true;
	}
	
	sort(Free + 1, Free + len + 1, cmp);
	for(int i = 1; i <= len; i++) 
		if(need[Free[i].index] && Free[i].t < dist[Free[i].index][0])
			need[Free[i].index] = false;
		else
			tim[++len2] = Free[i].t;
	for(int i = 0; i < mp[1].size(); i++)
		if(need[mp[1][i].v])
			ned[++len3] = dist[mp[1][i].v][0];
			
	if(len2 < len3)
		return false;
	sort(tim + 1, tim + len2 + 1);
	sort(ned + 1, ned + len3 + 1);
	int i = 1, j = 1;
	while(i <= len3 && j <= len2)
		if(tim[j] >= ned[i])
			i++, j++;
		else
			j++;
	if(i > len3)
		return true;
	return false;
}

int main() {
	int sum = 0;
	scanf ("%d", &n);
	Max = log2(n) + 1;
	for(int i = 1; i < n; i++) {
		int u, v, w;
		scanf ("%d %d %d", &u, &v, &w);
		Add_Edge(u, v, w);
		sum += w;
	}
	scanf ("%d", &m);
	for(int i = 1; i <= m; i++) 
		scanf ("%d", &query[i]);		
	init();
	LL l = 0, r = sum, ans = 0;
	while(l <= r) {
		LL mid = (l + r) >> 1;
		if(check(mid)) {
			r = mid - 1;
			ans = mid;
		}
		else
			l = mid + 1;
	}
	printf("%lld
", ans);
	return 0;
}