题解 P1084 【疫情控制】

· · 题解

貌似没有人用倍增？

那我来一发题解。

做法还是二分，然后通过倍增模拟。

对于能到达1号点的儿子的那些军队，扔到一个数组里sort一下。

然后贪心即可。

（自认为自己的代码很清楚一看就懂）

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define o 100001
using namespace std;
int head[o],nxt[o*2],point[o*2],weight[o*2],army[o],A[o],B[o],sign[o];
ll dis[o],f[o][22],d[o][22],remain[o]; 
bool son[o],build[o],ok[o];
int n,m,tot,ui,vi,wi;
vector<int> vec[60001];
void in(int &x){
    char c=getchar();bool b=0;x=0;
    while(c<'0'||c>'9'){if(c=='-')b=1;c=getchar();}
    while('0'<=c&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
    if(b)x=-x;
}
void addedge(int x,int y,int cap){
    tot++;nxt[tot]=head[x];head[x]=tot;point[tot]=y;weight[tot]=cap;
    tot++;nxt[tot]=head[y];head[y]=tot;point[tot]=x;weight[tot]=cap;
}
void dfs(int now,int dad){
    f[now][0]=dad;int cnt=0;
    if(now!=1){
        for(int i=1;i<=20;i++) f[now][i]=f[f[now][i-1]][i-1];
        for(int i=1;i<=20;i++) d[now][i]=d[f[now][i-1]][i-1]+d[now][i-1];
    }    
    for(int tmp=head[now];tmp;tmp=nxt[tmp]){
        int v=point[tmp];
        if(v!=dad){
            cnt++;
            dis[v]=dis[now]+weight[tmp];
            d[v][0]=weight[tmp];
            dfs(v,now);
        }
    }
    if(!cnt)son[now]=true;
}
bool cmpA(int x,int y){ return dis[x]<dis[y];}
bool cmpB(int x,int y){ return remain[x]<remain[y];}
bool Run(int now,int dad){
    if(son[now]){
        if(!build[now]) return ok[now]=false;
        else return ok[now]=true;
    }
    ok[now]=true;
    for(int tmp=head[now];tmp;tmp=nxt[tmp]){
        int v=point[tmp];
        if(v!=dad&&!build[v]&&!Run(v,now)) ok[now]=false;
    }
    return ok[now];
}
bool check(ll road){
    memset(build,0,sizeof(build));
    A[0]=B[0]=0;
    for(int tmp=head[1];tmp;tmp=nxt[tmp]) vec[point[tmp]].clear();
    for(int i=1;i<=m;i++)
    {
        int x=army[i];ll k=road;
        if(x==1){
            B[++B[0]]=i;
            remain[i]=k;
            continue;    
        }
        for(int j=20;j>=0;j--)
        if(f[x][j]>1&&d[x][j]<=k){
            k-=d[x][j];
            x=f[x][j];
            if(!k)break;
        }
        remain[i]=k;
        if(f[x][0]==1&&d[x][0]<remain[i]){
            remain[i]-=d[x][0];
            vec[x].push_back(i);
        }
        else build[x]=true,ok[x]=true; 
    }
    Run(1,0);
    if(ok[1])return true;
    for(int tmp=head[1];tmp;tmp=nxt[tmp]){
        int v=point[tmp];
        if(!ok[v]) A[++A[0]]=v;
        for(int x=0;x<vec[v].size();x++)B[++B[0]]=vec[v][x],sign[vec[v][x]]=v;
    }
    if(B[0]<A[0])return false;
    sort(A+1,A+A[0]+1,cmpA);
    sort(B+1,B+B[0]+1,cmpB);
    int la=1,lb=1;
    while(lb<=B[0]&&la<=A[0]){
        if(ok[A[la]]){ la++; continue; }
        while(remain[B[lb]]<dis[A[la]]&&lb<=B[0]&&sign[B[lb]]!=A[la]) ok[sign[B[lb++]]]=true;
        if(lb>B[0])break;
        lb++;la++;
    }
    while(ok[A[la]]&&la<=A[0])la++;
    return la>A[0];
}
int main(){
    in(n);
    for(int i=1;i<n;i++){
        in(ui),in(vi),in(wi); 
        addedge(ui,vi,wi);
    }
    in(m);
    for(int i=1;i<=m;i++) in(army[i]);
    dfs(1,0);
    ll l=0,r=1e12,mid,ans=-1;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld\n",ans);
}