Luogu P1084 疫情控制 题解

(Updated: )
oi
, , ,

Luogu Problem view

Describe

有一棵以$1$为根节点的树，现在要在除根节点外的点设立阻拦，使得没有一条路径可以从根节点到任意一个叶子节点。这些阻拦需要$m$个军队来设立，这$m$个军队中第$i$个一开始在点$q_i$上，军队移动的时间等于移动经过的边权之和，问最少要多少时间才能设立完阻拦。注意：不同的军队可以同时移动。 对于$100%$的数据，$2\leq m\leq n\leq 50,000,0\leq w\leq {10}^9$($w$表示边权)。

Solution

由题意可知，要求的是最少的时间，所以显而易见可以二分（如果花了更长的时间肯定更可以），接下来就只需要考虑如何写$check$函数。 我们有一个贪心的想法：因为要阻拦从根到叶子节点的路径，所以军队越往上肯定就越好，这样可以阻拦更多的路径。 如果一个军队可以走到根节点，则将这个军队先放一放，因为这个军队可能会走到另一个以根节点的子节点为根的树中去。 如果一个军队不可以走到根节点，则走到能走到的深度最小的点上。 经过这次操作后，再遍历一次，记录还是可以到达的叶子节点。再贪心的思想：剩余时间最少的军队到叶子节点肯定是最优的，然后再操作一遍，把剩余节点按照到根节点的距离进行排序。 现在可能还有一些军队还未设立阻拦，将这些军队按照剩余的时间进行排序，然后与刚刚排序过的剩余的节点一一匹配，这也是个贪心策略，如果所有都能够被匹配则可行，否则不可行。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#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();}