观察题目,答案明显具有单调性。
因为如果用$x$小时能够控制疫情,那么用$(x+1)$小时也一定能控制疫情。
由此想到二分答案,将问题转换为判断用$x$小时是否能控制疫情。
对于那些在$x$小时内不能够走到根节点的子节点上的军队,让他们尽量往上走即可,走到哪里是哪里,这样显然不会更劣。
对于那些在$x$小时内能走到根节点的子节点上的军队,就让他们先走到根节点的子节点上。
然后搞搞贪心即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;
struct edge
{
int last;
int end;
int weight;
}e[100005];
int n=0,m=0,ne=0;
int a[50005],note[50005],f[50005][20];
bool c[50005];
long long k1[50005],k2[50005],dis[50005];
vector<int> s[50005];
void NewEdge(int u,int v,int w)
{
ne++;
e[ne].last=note[u];
e[ne].end=v;
e[ne].weight=w;
note[u]=ne;
}
void dfs(int x,int fx)
{
for(int i=note[x];i;i=e[i].last)
if(e[i].end!=fx)
{
dis[e[i].end]=dis[x]+e[i].weight;
f[e[i].end][0]=x;
dfs(e[i].end,x);
}
}
void calc()
{
for(int j=1;j<=16;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
}
bool dfss(int x,int fx)
{
if(c[x]) return false;
bool flag=false;
for(int i=note[x];i;i=e[i].last)
if(e[i].end!=fx)
{
flag=true;
if(dfss(e[i].end,x)) return true;
}
if(!flag) return true;
return false;
}
bool check(long long x)
{
for(int i=1;i<=n;i++)
c[i]=false,s[i].clear();
for(int i=1;i<=m;i++)
{
int y=a[i];
long long w=0;
for(int j=16;j>=0;j--)
if(f[y][j]>1&&w+dis[y]-dis[f[y][j]]<=x)
w+=dis[y]-dis[f[y][j]],y=f[y][j];
if(f[y][0]==1) s[y].push_back(a[i]);
c[y]=true;
}
int cnt1=0,cnt2=0;
for(int i=note[1];i;i=e[i].last)
{
bool h=c[e[i].end];
c[e[i].end]=false;
bool t=dfss(e[i].end,1);
c[e[i].end]=h;
int len=s[e[i].end].size();
for(int j=0;j<len;j++)
{
if(t&&dis[s[e[i].end][j]]+e[i].weight>x)
{t=false;continue;}
k1[++cnt1]=x-dis[s[e[i].end][j]];
}
if(t) k2[++cnt2]=e[i].weight;
}
sort(k1+1,k1+cnt1+1);
sort(k2+1,k2+cnt2+1);
for(int i=1,j=1;i<=cnt2;i++)
{
while(j<=cnt1&&k1[j]<k2[i]) j++;
if(j>cnt1) return false;
j++;
}
return true;
}
int main()
{
scanf("%d",&n);
long long hi=0;
for(int i=1;i<=n-1;i++)
{
int u=0,v=0,w=0;
scanf("%d%d%d",&u,&v,&w),hi+=w;
NewEdge(u,v,w);
NewEdge(v,u,w);
}
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
dfs(1,0),calc();
long long l=-1,r=hi;
while(l+1<r)
{
long long mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
if(!check(r)) printf("-1");
else printf("%lld",r);
return 0;
}
Luogu P1084