Luogu P1084 疫情控制 题解

#include<bits/stdc++.h>
using namespace std;

#define re register 
#define N 50010
#define int long long 
#define File freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout)

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x+'0');
            else write(x/10),pc(x%10+'0');
        }
        #undef gc
        #undef pc
}I;

int n,m,logn,q[N];
vector<pair<int,int> > a; 
vector<int> v,g;

class Edge{
    public:
        int fir[N],nxt[N*2],son[N*2],w[N*2],tot;
        inline void add(int x,int y,int z){
            ++tot;
            nxt[tot]=fir[x];
            fir[x]=tot;
            son[tot]=y;
            w[tot]=z;
        }
}E;

class LCA{
    public:
        int f[N][25],dis[N][25],dep[N];
        inline void init(int x,int fa){
            dep[x]=dep[fa]+1;
            for(int i=0;i<logn;i++) f[x][i+1]=f[f[x][i]][i];
            for(int i=0;i<logn;i++) dis[x][i+1]=dis[x][i]+dis[f[x][i]][i];
            for(int to,i=E.fir[x];i;i=E.nxt[i]){
                to=E.son[i];
                if(to==fa) continue ;
                f[to][0]=x;dis[to][0]=E.w[i];
                init(to,x);
            }
        }
}L;

class Solve{
    private:
        int l,r,mid,ans,vis[N],una[N];
    public:
        inline int dfs(int x,int fa){
            if(vis[x]==1) return 1;
            re bool ff=0;
            for(int to,i=E.fir[x];i;i=E.nxt[i]){
                to=E.son[i];
                if(to==fa) continue ;
                ff=1;
                if(dfs(to,x)==0) return 0;
            }
            return ff;
        }
        inline int check(int Max){
            a.clear();
            v.clear();
            g.clear();
            memset(vis,0,sizeof(vis));
            memset(una,0,sizeof(una));
            for(int i=1;i<=m;i++){
                re int x=q[i],cnt=0;
                for(int j=logn;j>=0;j--){
                    if(L.f[x][j]>1&&cnt+L.dis[x][j]<=Max){
                        cnt+=L.dis[x][j];
                        x=L.f[x][j];
                    }
                }
                if(L.f[x][0]==1&&cnt+L.dis[x][0]<=Max) a.push_back(make_pair(Max-(cnt+L.dis[x][0]),x));
                else vis[x]=1;
            }
            for(int to,i=E.fir[1];i;i=E.nxt[i]){
                to=E.son[i];
                if(dfs(to,1)==0) una[to]=1;
            }
            sort(a.begin(),a.end());
            for(auto i=a.begin();i!=a.end();i++){
                if(una[(*i).second]==1&&(*i).first<L.dis[(*i).second][0]) una[(*i).second]=0;
                else v.push_back((*i).first); 
            }
            for(int to,i=E.fir[1];i;i=E.nxt[i]){
                to=E.son[i];
                if(una[to]==1) g.push_back(L.dis[to][0]); 
            }
            if(v.size()<g.size()) return 0;
            sort(v.begin(),v.end());
            sort(g.begin(),g.end());
            auto i=g.begin(),j=v.begin();
            while(i!=g.end()&&j!=v.end()){
                if((*j)>=(*i)) i++,j++;
                else j++;
            }
            return i==g.end();
        }
        inline void init(){
            n=I.read();logn=log2(n)+1;l=r=0;ans=-1;
            for(int x,y,z,i=1;i<n;i++){
                x=I.read(),y=I.read(),z=I.read();r+=z;
                E.add(x,y,z);
                E.add(y,x,z);
            }
            m=I.read();
            for(int i=1;i<=m;i++) q[i]=I.read();
            L.init(1,0);
        }
        inline void solve(){
            while(l<=r){
                mid=l+r>>1;
                if(check(mid)) ans=mid,r=mid-1;
                else l=mid+1;
            }
            I.write(ans);putchar('\n');
        }
}S;
signed main(){S.init();S.solve();}