P1084 [NOIP2012 提高组] 疫情控制
我们先考虑允许走到根的做法。
首先就是二分答案，然后每个军队尽可能往上跳跃，可以用倍增。（往下不优），最后检查是不是满足要求就行了。
不允许到根，所以可能有的军队需要支援其他地方。
我们先把不能到达根的点先原地驻扎。
此时，我们发现对于一个军队，如果它是剩余时间最少的点，且不能走到根再回来，那么我们选择原地驻扎。
- 如果用本来的点驻扎，那不如剩余时间少的点，可以把剩余时间多的用于支援。
- 如果是外来的点，那么这个点如果能到其他地方，那么说明那个地方的距离肯定小于原先位置到根的距离，那让外来点到这个点到的其他点上。
除此之外，其他点都可以被派遣（如果一个点还是回去，反正它可以去了再回，其实是等价的），那么每个其他点到根之后的剩余时间被求出，而且支援的点的距离也是有的，所以可以贪心的将剩余时间少的军队支援距离短的点。
复杂度 \(O(n\log n)\)。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l,i##end=r;i<i##end;++i)
#define Rs(i,l,r) for(int i=l,i##end=r;i>i##end;--i)
#define Le(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define Re(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define L(i,l) for(int i=0,i##end=l;i<i##end;++i)
#define E(i,l) for(int i=1,i##end=l;i<=i##end;++i)
#define W(t) while(t--)
#define Wh while
typedef long long ll;
const int N=50010,K=16,M=2*N;
const ll INF=5e13;
struct Army{
int ver;
ll rest;
bool is_del;
}army[N];
ll d[N];
bool g[N],st[N];
int n,m,f[N][K],q[N],p[N];
int h[N],e[M],ne[M],idx,w[M];//don't forget memset h!
void add(int a,int b,int c){
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void init(int x,int fa,ll dis){
d[x]=dis;
Ed{
int j=e[i];
if(j==fa)continue;
f[j][0]=x;
E(i, K-1)f[j][i]=f[f[j][i-1]][i-1];
init(j,x,dis+w[i]);
}
}
#define leaf(x) (!~ne[h[x]])
void dfs(int x,int fa,bool hv_army){
hv_army|=st[x];
if(leaf(x))g[x]=hv_army;
else{
g[x]=1;
Ed{
int j=e[i];
if(j==fa)continue;
dfs(j,x,hv_army);
if(!g[j])g[x]=0;
}
}
}
bool check(ll mid){
memset(st,0,sizeof st);
memset(g,0,sizeof g);
int cnt=0;
E(i, m){
int j=q[i];
Re(k, K-1, 0)
if(f[j][k]>1&&d[q[i]]-d[f[j][k]]<=mid)j=f[j][k];
if(d[q[i]]>mid)st[j]=1;
else army[++cnt]={j,mid-(d[q[i]]-d[j]),0};
}
dfs(1,-1,0);
memset(p,-1,sizeof p);
E(i, cnt){
int ver=army[i].ver;
if(!~p[ver]||army[p[ver]].rest>army[i].rest)p[ver]=i;
}
int x=1;
Ed{
int j=e[i];
if(!g[j]){
int k=p[j];
if(~k&&army[k].rest<d[army[k].ver]*2){
g[j]=1;
army[k].is_del=1;
}
}
}
int ncnt=0,gcnt=0;
E(i, cnt)
if(!army[i].is_del)army[++ncnt]=army[i];
Ed{
int j=e[i];
if(!g[j])p[++gcnt]=j;
}
sort(army+1,army+ncnt+1,[&](Army& x,Army& y){
return x.rest-d[x.ver]<y.rest-d[y.ver];
});
sort(p+1,p+1+gcnt,[&](int x,int y){
return d[x]<d[y];
});
int k=1;
for(int i=1;i<=ncnt&&k<=gcnt;i++)
if(army[i].rest-d[army[i].ver]>=d[p[k]])k++;
return k==gcnt+1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
memset(h,-1,sizeof h);
E(i, n-1){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
init(1,-1,0);
check(INF);
cin>>m;
E(i, m)cin>>q[i];
ll l=0,r=INF;
Wh(l<r){
ll mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<(r==INF?-1:r);
return 0;
}