题解 P1084 【疫情控制】

硫代硫酸钠 · 2018-03-12 15:03:13 · 题解

花了一上午敲完又花了一节课卡进1s其实是因为心态崩了干脆开了O_2优化

这道题的想法是

(暴力)

枚举所花费的时间,然后让军队暴力地向上跳

发现这两步都能优化

如果T秒可以部署完所有军队,T+1显然也行,只是浪费一些

据此可以二分答案.

然后跳跃也可以像找LCA那样倍增预处理

然后还需要一步贪心:

对于一个点,如果军队还能走的步数多,那么优先考虑用这些军队去建立检查站.

蒟蒻的代码

#include<bits/stdc++.h>
#define siz 500010
#define debug(x) cerr<<#x<<"="<<x
#define gc getchar()
#define tp to[p]
#define ll long long
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#define drep(i,n,s) for (register int i=n;i>=s;i--)
#define il inline
using namespace std;

il ll r()
{
    char c; ll x,f=1;
    for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
    for (c=gc;isdigit(c);c=gc) x=(x<<1)+(x<<3)+c-'0';
    return f*x;
}

int head[siz],to[siz],nxt[siz],num,len[siz],A[siz],B[siz];
int f[siz][25],dep[siz],n,m,rt,loc[siz];
ll g[siz][25],dis[siz],pos[siz],rem[siz];
bool sfi[siz],vis[siz],isleaf[siz],vis2[siz],sta[siz];
vector<int> tank[siz];

void add(int x,int y,int z)
{
    num++; to[num]=y; len[num]=z; nxt[num]=head[x];head[x]=num;
}

void dfs(int x)
{
    bool fg=0;
    for (int p=head[x];p;p=nxt[p])
      if (!vis[tp])
      {
        fg=1;dep[tp]=dep[x]+1;dis[tp]=dis[x]+len[p];
          f[tp][0]=x;g[tp][0]=len[p];vis[tp]=1;dfs(tp);
      }
    if (!fg) isleaf[x]=1;
}

void bz()
{
    rep(j,1,16) rep(i,1,n) f[i][j]=f[f[i][j-1]][j-1];
    rep(j,1,16) rep(i,1,n) g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]; 
}

bool cmp1(int x,int y) {return dis[x]<dis[y];}
bool cmp2(int x,int y) {return rem[x]<rem[y];}

bool isclean(int x,int fa)
{
    if (isleaf[x])
        if (!sfi[x]) return sta[x]=0;
            else return sta[x]=1;
    sta[x]=1;
    for (int p=head[x];p;p=nxt[p])
            if (tp!=fa&&!sfi[tp]&&!isclean(tp,x)) sta[x]=0; 
    return sta[x];      
}

bool judge(ll road){
    memset(sfi,0,sizeof(sfi));
    int ant=0,bnt=0;
    for(int p=head[1];p;p=nxt[p]) tank[tp].clear();
    for(int i=1;i<=m;i++)
    {
        int x=pos[i];ll k=road;
        if(x==1)
        {
            B[++bnt]=i;
            rem[i]=k;
            continue;    
        }
        for(int j=20;j>=0;j--)
        if(f[x][j]>1&&g[x][j]<=k)
        {
            k-=g[x][j];
            x=f[x][j];
            if(!k)break;
        }
        rem[i]=k;
        if(f[x][0]==1&&g[x][0]<rem[i])
        {
            rem[i]-=g[x][0];
            tank[x].push_back(i);
        }
        else sfi[x]=true,sta[x]=true; 
    }
    bool b=isclean(1,-1);
    if(sta[1])return true;
    for(int p=head[1];p;p=nxt[p])
    {      
        if(!sta[tp]) A[++ant]=tp;
        for(int x=0;x<tank[tp].size();x++)B[++bnt]=tank[tp][x],loc[tank[tp][x]]=tp;
    }
    if(bnt<ant)return false;
    sort(A+1,A+ant+1,cmp1);
    sort(B+1,B+bnt+1,cmp2); 
    int posA=1,posB=1;
    while(posB<=bnt&&posA<=ant){
        if(sta[A[posA]]){ posA++; continue; }
        while(rem[B[posB]]<dis[A[posA]]&&posB<=bnt&&loc[B[posB]]!=A[posA]) 
        sta[loc[B[posB++]]]=true;
        if(posB>bnt)break;
        posB++;posA++;
    }
    while(sta[A[posA]]&&posA<=ant)posA++;
    return posA>ant;
}

int main()
{

    n=r(); rt=1;
    rep(i,1,n-1) 
    {
        int x=r(),y=r(),z=r(); add(x,y,z); add(y,x,z);
    } 
    dep[rt]=1; vis[rt]=1;  dfs(rt);bz(); m=r();
    rep(i,1,m) pos[i]=r(); 
    ll lb=0,rb=1e15,mid,ans=-1;
    while (lb<=rb)
    {
        mid=(lb+rb)>>1;
        if (judge(mid)) ans=mid,rb=mid-1;
        else lb=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}