题解 P1084 【疫情控制】
VPYEKINDAR · · 题解
这题的复杂程度实属厉害 思路-对于一个军队，他要么给定的时间内走到该子树顶(1根之下一个)或者通关根1走到其他子树顶，如果有足够时间，这样的方案之一一定最优，所以主要就是处理这两个，我寻思这一点其他题解没说明白 下面给出做法与证明 对于到主根的军队，对其剩余时间从小到大排序，如果其剩余时间小于！等！（特别强调）于其到原本子树顶时间且该子树需要军队，就让其盖住其原子树顶。
证明：如果这个军队不去的话一定有剩余时间比这个军队多的来尝试阻断，而多了一个剩余时间较少的军队（哪怕另外一个也是原子树的），所以这样就明显不利总体阻断。 这样的话，我们就可以二分O(logn)，倍增判断O(nlogn)，就可以在O(nlog²n)时间解决本题. 经总结 有4种(lca)一种朴素lca 还有两个求两点最大值最小值的lca(见货车运输)，还有这题的求边权和的lca了 还有两个坑点 1.r设为远大于50000的数。 2.在check中最好判断到1的点<要阻断的点时return 0的情况，我的代码会出锅- -，但是希望诸位打的没有。 还有一点不知道要不要说 在判断从根回子树顶的时候，最好新开一个数组来表示他的剩下能到1的军队，否则做起来用数组比较麻烦，预计用链表会很方便，无奈本人实在无能掌握此等复杂指针。 说了这么多，我的程序说实话都是一些基础语法应该各位没什么困难看懂
代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct z{
int pt,w;
}sw[50001];
ll sign,las[50001],dis[50001][21];
int orz,vt[50001],k1,cnt,reach[50001],du[50001],suck[50001],rot[50001],snd[50001],jp[50001],ar[50001],tp[50001],m,d[50001],p[50001][21],k,n,head[200010];
struct p{
int v,w,next;
}st[100051];
struct qq{
int v;
}st1[100001];
struct q{
int older,biao,v,s,el;
}ed[50001];
int add(int a,int b,int c){
st[++k].v=b;
st[k].w=c;
st[k].next=head[a];
head[a]=k;
}
int cmp(z a,z b)
{
return a.w>b.w;
}
int cmp2(q a,q b){
return a.v<b.v;
}
int cmp3(qq a,qq b){
return a.v>b.v;
}
int dfs(int u,int fa,ll we)
{
d[u]=d[fa]+1;
p[u][0]=fa;
dis[u][0]=we;
for(int i=1;(1<<i)<d[u];i++)
{
p[u][i]=p[p[u][i-1]][i-1];
dis[u][i]=dis[p[u][i-1]][i-1]+dis[u][i-1];
//printf("%d %d %d\n",u,i,dis[u][i]);
}
for(int i=head[u];i;i=st[i].next){
int v=st[i].v;
if(v==fa)continue;
dfs(v,u,st[i].w);
}
}
int dfs2(int u){
//printf("%d %d\n",u,d[u]);
if(d[u]==2){
return u;
}
for(int i=head[u];i;i=st[i].next){
int v=st[i].v;
if(d[v]==d[u]-1)return dfs2(v);
}
}
int dfs3(int u){
//printf("%d\n",u);
if(suck[u])return 0;
if(du[u]==1){
sign=1;return 0;
}
for(int i=head[u];i;i=st[i].next){
int v=st[i].v;
if(d[v]==d[u]+1)
dfs3(v);
}
}
int check(int lim){
for(int i=1;i<=50000;i++)
ed[i].v=0;
memset(reach,0,sizeof(reach));
memset(suck,0,sizeof(suck));
memset(ar,0,sizeof(ar));
for(int i=1;i<=m;i++)
jp[i]=tp[i];
k1=0;
orz=0;
for(int i=1;i<=m;i++){
int k=lim;
for(int j=20;j>=0;j--){
if(dis[jp[i]][j]<=k){
k-=dis[jp[i]][j];
jp[i]=p[jp[i]][j];
//printf("%d %d\n",jp[i],j);
}
if(jp[i]==1){
k1++,ed[k1].biao=k1,ed[k1].v=k,las[i]=k;
ed[k1].older=snd[tp[i]];
ed[k1].el=vt[snd[tp[i]]];//printf("%d %d %d\n",k1,ed[k1].el,ed[k1].v);
ar[i]=1;
break;
}
}
}for(int i=1;i<=m;i++){
// printf("--%d\n",jp[i]);
suck[jp[i]]=1;}
suck[1]=0;
for(int i=1;i<=cnt;i++){
sign=0;
//printf("%d ",sw[i].pt);
dfs3(sw[i].pt);
if(sign){
reach[sw[i].pt]=1;orz++;}
//printf("%d %d-\n",sw[i].pt,reach[sw[i].pt]);
//printf("%d %d",sw[i].pt,reach[sw[i].pt]);
}
if(k1<orz)return 0;
int k2=0;
sort(ed+1,ed+k1+1,cmp2);
for(int i=1;i<=k1;i++)
{
if(ed[i].v<=ed[i].el&&reach[ed[i].older]){
reach[ed[i].older]=0;
}
else{
k2++;
st1[k2].v=ed[i].v;
}
}
//for(int i=1;i<=k2;i++)
//printf("%d\n",st1[i].v);
//for(int i=1;i<=k1;i++)
//printf("%d %d %d %d %d\n",ed[i].biao,ed[i].el,ed[i].older,ed[i].s,ed[i].v);
sort(st1+1,st1+k2+1,cmp3);
//for(int i=1;i<=k2;i++)
//printf("%d\n",st1[i]);
//for(int i=1;i<=k1;i++)
//printf("%d %d %d %d\n",ed[i].biao,ed[i].el,ed[i].older,ed[i].v);
int aim=0;
for(int i=1;i<=cnt;i++){
//printf("%d %d %d\n",reach[sw[i].pt],sw[i].pt,sw[i].w);
if(reach[sw[i].pt]){
aim++;
//printf("%d %d\n",sw[i].pt,reach[sw[i].pt]);
if(st1[aim].v<sw[i].w)
return 0;
}
}
return 1;
//for(int i=1;i<=m;i++)
//printf("%d ",ar[i]);
}
int main()
{
memset(dis,0x3f,sizeof(dis));
int a,b,c;
cnt=0;
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
if(b<a)swap(a,b);
add(a,b,c);
add(b,a,c);
du[a]+=1,du[b]+=1;
//printf("%d %d %d\n",a,b,c);
if(a==1){
vt[b]=c;
cnt++;
sw[cnt].pt=b;
sw[cnt].w=c;
//printf("%d %d %d\n",cnt,sw[cnt].pt,sw[cnt].w);
}
}
sort(sw+1,sw+1+cnt,cmp);
dfs(1,0,0);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&tp[i]); snd[tp[i]]=dfs2(tp[i]);
//printf("snd%d\n",snd[i]);
}
int l=0,r=150001;
while(l<=r){
int mid=(l+r+1)/2;
if(check(mid))r=mid-1;
else l=mid+1;
}
cout<<l;
//for(int i=1;i<=n;i++)
//printf("%d ",suck[i]);
}```