luogu1084 [NOIp2012]疫情控制 (二分答案+倍增+dfs序)

时间:2023-01-23 19:11:14

先二分出一个时间,把每个军队倍增往上跳到不能再跳

然后如果它能到1号点,就记下来它跳到1号点后剩余的时间;如果不能,就让它就地扎根,记一记它覆盖了哪些叶节点(我在这里用了dfs序+差分,其实直接dfs就行..)

然后对于那些叶节点没有被覆盖完全的(父亲为1号点的)子树,肯定需要一些已经到1号点的军队来走过去

如果它离1距离越远,肯定就希望用剩余时间越多的军队来走,除非是有一个剩余时间更少的军队本来就在这个子树里

看一看能不能符合要求的就行了

然而有很多要注意的地方:

0.一个军队只能用一次......(开始读错题 还在想为什么会有-1的情况)

1.只需要覆盖叶节点就行了,也就是说,统计这个子树有没有完全被覆盖的时候,不能统计到非叶节点

2.即使有军队本来在这个子树里,我也有可能不选这个军队来到这个子树里,因为它的剩余时间可能非常大

3.有可能到1号点的军队数不足覆盖掉那些没被覆盖的子树,这时候也是-1

4.每次judge要清零...

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=5e4+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Edge{
int b,ne;ll l;
}eg[maxn*];
int egh[maxn],ect;
int N,M,p[maxn];
int dfn[maxn][],tot,fa[maxn][];
int bel[maxn],cnt[maxn],tmp[maxn],tmp2[maxn];
int mim[maxn],id[maxn];
bool flag[maxn],islef[maxn];
ll dis[maxn][],rest[maxn]; inline void adeg(int a,int b,ll l){
eg[++ect].b=b;eg[ect].l=l;eg[ect].ne=egh[a];egh[a]=ect;
} void dfs(int x){
dfn[x][]=++tot;id[tot]=x;
for(int i=;fa[x][i]&&fa[fa[x][i]][i];i++){
fa[x][i+]=fa[fa[x][i]][i];
dis[x][i+]=dis[x][i]+dis[fa[x][i]][i];
}islef[x]=;
for(int i=egh[x];i;i=eg[i].ne){
int b=eg[i].b;
if(b==fa[x][]) continue;
fa[b][]=x;dis[b][]=eg[i].l;
if(x==) bel[b]=b;
else bel[b]=bel[x];
dfs(b);
islef[x]=;
}
dfn[x][]=tot;
} int getfe(int x,ll &lim){
for(int i=;i>=;i--){
if(fa[x][i]&&dis[x][i]<=lim) lim-=dis[x][i],x=fa[x][i];
}
return x;
} inline bool cmp(int a,int b){return rest[a]>rest[b];}
inline bool cmp2(int a,int b){return dis[a][]>dis[b][];} inline bool judge(ll m){
// printf("!!%lld:\n",m);
int n,i,j;
CLR(cnt,);
for(i=,j=;i<=M;i++){
rest[i]=m;
int x=getfe(p[i],rest[i]);
// printf("%d %d %lld\n",p[i],x,rest[i]);
if(x==) tmp[++j]=i;
else{
cnt[dfn[x][]]++;
cnt[dfn[x][]+]--;
}
}
n=j;sort(tmp+,tmp+n+,cmp);
CLR(flag,);
for(i=,j=;i<=N;i++){
j+=cnt[i];
if(j==&&islef[id[i]]) flag[bel[id[i]]]=;
}
CLR(mim,);
for(i=n;i;i--){
if((!flag[bel[p[tmp[i]]]])&&(!mim[bel[p[tmp[i]]]])){
mim[bel[p[tmp[i]]]]=i;
}
}
for(i=,j=;i<=N;i++){
if(fa[i][]!=||flag[i]) continue;
tmp2[++j]=i;
}m=j;
sort(tmp2+,tmp2+m+,cmp2);
if(n<m) return ;
for(i=,j=;i<=n&&j<=m;i++){
if(!tmp[i]) continue;
if(tmp[mim[tmp2[j]]]){
tmp[mim[tmp2[j]]]=;
i--;
}else{
if(rest[tmp[i]]<dis[tmp2[j]][]) return ;
tmp[i]=;
}j++;
}
return j>m;
} int main(){
// freopen("testdata (1).in","r",stdin);
int i,j,k;
N=rd();
for(i=;i<N;i++){
int a=rd(),b=rd(),c=rd();
adeg(a,b,c);adeg(b,a,c);
}dfs();
M=rd();
for(i=;i<=M;i++) p[i]=rd();
ll l=,r=1e15,ans=1e15+;
while(l<=r){
ll m=l+r>>;
if(judge(m)) ans=m,r=m-;
else l=m+;
}
if(ans==1e15+) printf("-1\n");
else printf("%lld\n",ans);
return ;
}