P1084 疫情控制

发表于

闲扯

好久没有写闲扯了

这道题从昨天开始改，一直没过，突然间看到一篇题解，恍然大悟，终于改过了。。。

我的内心：mmp，这hs出题人

题面

P1084 疫情控制

Solution

因为可以同时移动，而且询问最少需要多久，更重要的是答案具有单调性，所以妥妥的二分答案。

那么问题就变成了怎么判断在 $lim$ 的时限内，完成对叶节点的管控。

首先，我们有一个贪心的想法：对于一个点，如果我们肯定要将它尽量的向上放。因为深度越小，能管控的叶子节点的数目一定是单调不减的。

然后我们需要分一下情况来讨论。

  1. 如果当前节点不能到达根结点，那么我们就跳到第一个能跳到的节点。
  2. 如果刚好能跳到根结点，那么我们就跳到这条链上根结点的子节点。
  3. 如果能跳到根结点，但是剩余的时间内没法跳到这条链上根结点的子节点，且前两种情况没有将它所在的子树中的叶节点全部管控，就跳回去。

剩下的根结点的子树中，如果还有叶节点没管控完的，我们就找剩下的，能跨过根结点的节点中，离它最近的一个。

为了方便处理叶节点是否管控完，我们先记录一下每一个点为根，包含了几个叶节点，然后用树状数组维护一下子树中已经管控了几个点（利用 $dfn$ 的性质）即可。

Code

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 5e4+5;
int n,m,u,v,d,head[MAXN],num_edge,deg,num[MAXN],army[MAXN];
ll l,r,dis[MAXN];
struct Edge{
	int next,to,dis;
	Edge(){}
	Edge(int next,int to,int dis):next(next),to(to),dis(dis){}
}edge[MAXN<<1];
il add_edge(int u,int v,int dis){
	edge[++num_edge]=Edge(head[u],v,dis),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u,dis),head[v]=num_edge;
}
int dep[MAXN],f[MAXN][18],lg2[MAXN],dfn[MAXN],sz[MAXN],cnt;
il DFS(int u,int fa){// get dis and num.
	ri fla=0;f[u][0]=fa,dep[u]=dep[fa]+1,dfn[u]=++cnt,sz[u]=1;
	for(ri i=1;(1<<i)<=dep[fa];++i) f[u][i]=f[f[u][i-1]][i-1];
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;fla=1;
		dis[edge[i].to]=dis[u]+edge[i].dis,DFS(edge[i].to,u);
		num[u]+=num[edge[i].to],sz[u]+=sz[edge[i].to];
	}
	if(!fla) num[u]=1;
}
it find(int u,ll dist){
	for(ri i=lg2[dep[u]];i>=0;--i){
		if(!f[u][i]) continue;
		if(dis[u]-dis[f[u][i]]<=dist) dist-=dis[u]-dis[f[u][i]],u=f[u][i];
	}
	return u;
}
int get[MAXN],tr[MAXN],T[MAXN];
il updata(int pos,int k){for(;pos<=n;pos+=lowbit(pos)) T[pos]+=k;}
it query(int pos){ri res=0;for(;pos;pos-=lowbit(pos)) res+=T[pos];return res;}
multiset<ll> s;
il DFS1(int u,int fa,int ty){
	ri fla=0;
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		DFS1(edge[i].to,u,ty|tr[u]);
		get[u]+=get[edge[i].to],fla=1;
	}
	if(!fla) get[u]=ty|tr[u];
}
int a[MAXN],tot;
inl bool cmp1(int x,int y){return dis[x]<dis[y];}
it check(ll lim){
	s.clear(),del(tr,0),del(get,0),del(T,0),tot=0;
	for(ri i=1;i<=m;++i){
		u=army[i];
		if(lim>dis[u]) s.insert(lim-dis[u]);
		else{
			ri pos=find(u,min(dis[u]-1,lim));
			ri tot=query(dfn[u]+sz[u]-1)-query(dfn[u]);
			if(!tr[pos]&&num[u]>tot) tr[pos]=1,updata(dfn[u],num[u]-tot);
		}
	}
	for(ri i=1;i<=m;++i){
		u=army[i];
		if(lim>dis[u]){
			ri pos=find(u,min(dis[u]-1,lim));
			ri tot=query(dfn[u]+sz[u]-1)-query(dfn[u]);
			if(!tr[pos]&&num[u]>tot&&lim-dis[u]<dis[pos]) tr[pos]=1,updata(dfn[u],num[u]-tot),s.erase(s.find(lim-dis[u]));
		}
	}
	DFS1(1,0,0);
	for(ri i=head[1];i;i=edge[i].next)
		if(get[edge[i].to]!=num[edge[i].to]){
			multiset<ll>::iterator ite=s.lower_bound(dis[edge[i].to]);
			if(ite==s.end()) return 0;
			s.erase(ite);
		}
	return 1;
}
inl bool cmp(int x,int y){return dis[x]>dis[y];}
int main(){
//	freopen("testdata.in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(ri i=1;i<n;++i){
		read(u),read(v),read(d),add_edge(u,v,d);
		if(u==1||v==1) ++deg;
		r+=d;
	}
	read(m);
	for(ri i=1;i<=m;++i) read(army[i]);
	if(deg>m) return puts("-1"),0;
	for(ri i=2;i<=n;++i) lg2[i]=lg2[i>>1]+1;
	DFS(1,0),sort(army+1,army+1+m,cmp);
	while(l<r){
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	print(l);
	return 0;
}

总结

在考虑不同情况时一定要想好怎么才是最优的，不然写着写着就挂了。