题解 P1084 【疫情控制】
Makasukaka · · 题解
疫情控制题解
前言
前后断断续续一个星期，终于把这题结果了。期间无数次WA，今天晚上我终于把它想清楚了。在此写篇题解，既是纪念，也是总结。
题目大意
观察一下题目就可以知道，这一题是要求一个最短时间t。满足军队在t秒内可以移动到除了根的点，使所有的叶子节点到根的路径都被军队覆盖。
分析
1：时间t一定是满足单调性的，因为边权非负，如果t时间内可以满足题目要求的话，那么大于t的也一定满足。
2：所以二分时间t理所当然。既然是二分，那t一定一开始有个界限。什么时候会无解呢？那就是军队个数小于第一层孩子的时候。你无论多大的时间t，都不可能覆盖完全部的孩子。
3:处理完无解的情况，我们来想想二分的界限。一个宽松的最大时间t是所有边权和。这个tmax一定可以让所有军队移动到第一层。
4：那么我们就需要判断当前的t是否满足要求。我们记录dep[x]表示x这个点到根的深度，可以显然得知，军队一定是尽力在t时间内跳到dep小的点。
5：那么问题又来了，因为不能驻扎在根，那么我们如果具备跳到根的实力的话，一定要选一个第一层的孩子下放。这就面临一个军队是待在当前子树，还是途径根到另外一颗子树的抉择。
6：我们假设当前二分的时间是curt。我们把在curt时间内可以到达根的军队拿出来，算出还剩余的时间lst。对于根的每一个子树x，我们维护一个struct x表示在这个子树内的军队，到子树根x后还剩下的时间的最小值mov。因为如果要是待在子树里的话，一定是最不能向上跑的待在子树里。
7：那么，我们如何判断一个子树是被它自己的c的值覆盖，还是另外一个子树的点跳过来覆盖它呢?这里是最不好想的地方。先说结论，对于一个子树x，x中的mov如果<=2dep[x]的话，那么这个子树一定是被mov覆盖，而不是被其他树的点覆盖。为什么呢？如果mov<=2dep[x]的话，那么mov对应的这个军队，如果再跳上根的话，它只能覆盖dep比x更小的。相当于资源的浪费，不如就待在x让它的价值能最被利用上。
8: 我们把不能跳到根的军队的最大提升的距离处打一个tag, 一次dfs可以求出还有哪些一层子节点需要被覆盖。再把第7步提到的点单独处理。对于可以跳到根，且没有被第7步使用的军队点。把它按lst从大到小排序，第一层子节点也按dep从大到小排序，依次暴力配对就行了。总的复杂度是O（n(logn)^2）的样子。
9：至此，我们已经解决了这道题的所有思维难题。接下来就是一些细节啦！
10:关于向上跳的操作。可以方便的使用树上倍增来实现。这题还要注意的是sort的先后，因为sort过后，军队的次序就改变了，之前的used标记就是错的。被这坑了好几次。
附上本人巨丑无比的代码。实在是删删改改改烦了，一直在补丁补丁。
#include<cstdio>
#include<algorithm>
#include<iostream>
const int N=5e5+5;
using namespace std;
typedef long long LL;
int v[N],nxt[N<<1],head[N],w[N<<1],tot;
int n,m,cnt;
int f[N][20],dep[N],p[N],fp[N],visv[N],tag[N],ttot;
int used[N];
LL L,R,wdep[N];
struct poi{
int x,lst,pos,mov;
}a[N],b[N],c[N];
inline void add(int x,int y,int z){
v[++tot]=y;
w[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int opt=0;
inline void dfs(int x,int fa){
visv[x]=1;
for(int i=1;i<=19;++i){
if(dep[x]>=(1<<i))f[x][i]=f[f[x][i-1]][i-1];
else break;
}
for(int i=head[x];i;i=nxt[i]){
int y=v[i];
if(y!=fa&&!visv[y]){
dep[y]=dep[x]+1;
wdep[y]=wdep[x]+w[i];
f[y][0]=x;
dfs(y,x);
}
}
}
inline void dfs3(int x,int fa){
int cur=-1;
for(int i=head[x];i;i=nxt[i]){
int y=v[i];
if(y!=fa){
dfs3(y,x);
if(cur==-1)cur=tag[y];
else cur&=tag[y];
}
}
if(cur!=-1)tag[x]|=cur;
}
inline int cmp(const poi &a,const poi &b){
return a.lst>b.lst;
}
inline int check(LL mxt){
for(int i=1;i<=m;++i){
LL curt=mxt;int curp=p[i],fl=0;
for(int j=19;j>=0;--j){
if((dep[curp]>=(1<<j))&&(curt>=wdep[curp]-wdep[f[curp][j]])){
if(f[curp][j]==1){//can to the capital
a[++ttot].x=i;
a[ttot].pos=curp;
a[ttot].mov=curt-(wdep[curp]-wdep[fp[curp]]);
a[ttot].lst=curt-wdep[curp];
fl=1;
break;
}
else{//up
curt-=(wdep[curp]-wdep[f[curp][j]]);
curp=f[curp][j];
}
}
}
if(!fl){
tag[curp]=1;
}
}
dfs3(1,1);
int j=1,jj=1;//j表示当前扫到了哪个军队,jj就是一个判断标志。
sort(a+1,a+1+ttot,cmp);//从大到小按lst排序
for(int i=1;i<=ttot;++i){
used[i]=0;
if(!c[a[i].pos].x||c[a[i].pos].lst>a[i].mov){//计算子树内的最小lst
c[a[i].pos].x=i;
c[a[i].pos].lst=a[i].mov;
}
}
for(int i=1;i<=cnt;++i){
if(!tag[b[i].x]){
if(c[b[i].x].x&&c[b[i].x].lst<=2*b[i].lst){//如第7步
used[c[b[i].x].x]=1;
continue;
}
while(j<=ttot&&(a[j].lst<b[i].lst||used[j]))j++;
if(j<=ttot&&a[j].lst>=b[i].lst)used[j]=1;
else{
jj=0;
break;
}
}
}
if(jj)return 1;
else return 0;
}
inline void reset(){
ttot=0;
for(int i=1;i<=n;++i)tag[i]=0,used[i]=1;
for(int i=1;i<=n;++i)c[i].x=0;
}
inline void dfs2(int x,int fa,int id){
fp[x]=id;
for(int i=head[x];i;i=nxt[i]){
int y=v[i];
if(y!=fa){
dfs2(y,x,id);
}
}
}
int main(){
n=read();
for(int i=1;i<n;++i){
int x=read(),y=read(),z=read();
add(x,y,z);add(y,x,z);
if(x==1||y==1){
if(x>y)swap(x,y);
b[++cnt].lst=z;
b[cnt].x=y;
}
R+=z;
}
R++;
sort(b+1,b+1+cnt,cmp);
dfs(1,1);
m=read();
for(int i=1;i<=m;++i)p[i]=read();
if(cnt>m){puts("-1");return 0;}
for(int i=head[1];i;i=nxt[i]){
int y=v[i];
dfs2(y,1,y);
}
while(L<R){
reset();
LL mid=(L+R)/2;
if(check(mid))R=mid;
else L=mid+1;
}
printf("%lld\n",L);
return 0;
}