【NOIP2012提高组】疫情控制

题面

大多数人引理给的都很突兀啊。

首先意识到答案单调性。这启发我们尝试二分答案。

然后在剩余时间固定的情况下,我们会发现一个点肯定往上走可以控制更多叶子。但是注意有些点可以跨过根,去到根上挂着的别的子树(根上挂着的子树称之为“根子树”)。

一个显然的想法是把剩余的根子树和还能动军队的拿出来,然后排序后贪心。但是这带来一个问题:如果当前军队属于当前根子树,理论上我可以把它直接扔到这颗根子树,但是我们会判断错误。

举个例子:假设当前军队还有时间 \(5\) 可以行动,位于根节点的儿子节点 \(2\),\(<1,2>\) 的连边长度为 \(3\). 就会产生错误,因为我们默认每个军队先走到根节点再走下去到别的子树。

所以我们能否解决那些剩余时间不足以从当前根子树的根走到 \(1\) 再回来的军队。如果能,剩下的军队就可以用上述方法贪心。

所以引出一个引理:这类军队一定会待在这个根而不是移动到其它根子树上。

简单证明: 如果移动这样的一个军队 \(s\),它原来的位置需要另一个军队,这个军队 \(s'\) 从别的根子树过来,所以 \(s\) 能到的 \(s'\) 也能到。但是 \(s'\) 能到的 \(s\) 不一定能到。这个时候显然我们会让 \(s\) 优先选择这个位置。

LOJ加强版因为写了vector被卡常了

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
#define next Cry_For_theMoon
#define il inline
#define pb(x) push_back(x)
#define is(x) insert(x)
#define sit set<int>::iterator
#define mapit map<int,int>::iterator
#define pi pair<int,int>
#define ppi pair<int,pi>
#define pp pair<pi,pi>
#define fr first
#define se second
#define vit vector<int>::iterator
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
using namespace std;
const ll MAXN=3e5+10,MAXM=6e5+10,INF=4e14; 
struct Edge{int u,v,w;}edge[MAXM];
int first[MAXN],next[MAXM];
int n,m,u,v,w;
int color[MAXN],vis[MAXN];
int fa[MAXN][20],depth[MAXN];
ll faw[MAXN][20];
vector<ll>v1,v2,v3;
vector<pair<ll,ll> >tmp;
void addedge(int u,int v,int w){
	static int tot=0;edge[++tot]=(Edge){u,v,w};next[tot]=first[u];first[u]=tot;
}
void dfs(int u){
	rep(j,1,19){fa[u][j]=fa[fa[u][j-1]][j-1];faw[u][j]=faw[u][j-1]+faw[fa[u][j-1]][j-1];}
	for(int j=first[u];j;j=next[j]){
		int v=edge[j].v;
		if(v==fa[u][0])continue;
		fa[v][0]=u,faw[v][0]=edge[j].w;depth[v]=depth[u]+1; 
		dfs(v);
	}
}
void dfs2(int u){
	int flag=0;
	color[u]=1;
	for(int j=first[u];j;j=next[j]){
		int v=edge[j].v;if(v==fa[u][0])continue;flag=1;
		dfs2(v);color[u]&=color[v];
	}
	color[u]|=vis[u];
	if(!flag)color[u]=vis[u];
}
void Leap(ll mid){
	for(vector<ll>::iterator it=v1.begin();it!=v1.end();it++){
		ll u=*it,rest=mid;
		per(j,19,0){
			if(depth[fa[u][j]]>=2 && rest>=faw[u][j])rest-=faw[u][j],u=fa[u][j];
		}
		if(depth[u]==2)tmp.pb(mp(u,rest));
		else vis[u]=1;
	}
}
bool Greedy(ll mid){
	int size1=v2.size(),size2=v3.size(),L=0,R=0;
	if(!size2)return true;
	while(L<size1){
		if(v2[L]>=v3[R])R++;
		if(R>=size2)return true;
		L++;
	}
	return false;
}
bool check(ll mid){
	//初始化 
	v2.clear();v3.clear();tmp.clear();memset(color,0,sizeof color);memset(vis,0,sizeof vis);
	//对于每支军队倍增去跳
	Leap(mid);
	//统计剩余子树情况 
	dfs2(1);
	int size=tmp.size();
	rep(i,0,size-1){
		if((tmp[i].se>=2*faw[tmp[i].fr][0]) || 
		(tmp[i].se>=faw[tmp[i].fr][0] && color[tmp[i].fr]))v2.pb(tmp[i].se-faw[tmp[i].fr][0]);
		else color[tmp[i].fr]=1;
	}
	rep(i,1,n){if(depth[i]!=2 || color[i])continue;v3.pb(faw[i][0]);}
	sort(v2.begin(),v2.end());sort(v3.begin(),v3.end());
	//贪心
	return Greedy(mid); 
}
void Read(int& num){
	char ch;while((ch=getchar()) && !isdigit(ch));
	num=ch-'0';
	while((ch=getchar()) && isdigit(ch))num=num*10+ch-'0'; 
} 
int main(){
	Read(n);
	rep(i,1,n-1){
		Read(u);Read(v);Read(w);addedge(u,v,w),addedge(v,u,w);
	}
	Read(m);
	int tmp;
	rep(i,1,m){Read(tmp);v1.pb(tmp);}
	depth[1]=1;dfs(1);
	ll L=0,R=INF,ans=-1;
	while(L<=R){
		ll mid=(L+R)>>1;
		if(check(mid)){ans=mid;R=mid-1;
		}else{L=mid+1;}
	}
	printf("%lld",ans);
	return 0;
}
上一篇:P1083 [NOIP2012 提高组] 借教室


下一篇:【NOIP2012提高组】开车旅行