题解 P1084 【疫情控制】

## 总体思路 先说输出-1的情况，也就是军队数小于根节点的子节点数时无法完成控制，输出-1 接下来，对于求最小时间就想到了可以二分答案。二分限制的时间t，看是否所有军队是否能在t时间内完成移动。 那么时候涉及到树上移动，为了不超时，我们显然需要倍增来爬树。 剩下的就是怎么判断能否在t时间内完成移动了，这道题主要就是这里烦人 ------------ ## 判断做法 很显然的可以想到，所有军队都要尽量往上爬，因为越往上，能控制的节点就越多。 主要问题在于，要不要跨子树。 那么对于所有能爬到根节点的军队，我们记下他剩下的时间和原先爬上来的子树。如果这个军队所在的子树并没有被控制，并且他剩余时间不够他回到原来的子树，那他就根本不用爬到根节点，让他回去控制原来的子树就可以了。因为如果他不回去，必然需要另一个到达根节点并且剩余时间大于从根节点到他原来的子树距离的军队来代替他控制那颗子树，这样显然是亏的，因为当前军队的剩余时间小于子树到根节点距离，也就是小于能代替他控制子树的军队的剩余时间。让一个剩余时间大于当前军队的军队代替当前军队控制当前子树显然不合理。 ### SO~ 上述情况是要回去滴 怎么写呢？把爬到根节点的军队按照剩余时间从小到大排序，然后对于满足上述情况的点，把他原先所在的子树做标记，并把剩余时间赋为-1即可。至于为什么要从小到大排序：当两个点原先的子树为同一棵的情况下，当然让剩余时间小的那个去控制原来那棵子树啦，大的那个后扫到，此时原来的子树已经被小的军队控制了，他就不用回去了。 ### Then~ 那么对于仍然还呆在根节点等你安排的军队，把他们按照剩余时间从大到小排序。然后记录一下根节点到所有没有被控制的子树的距离，也从大到小排序。然后，贪心比较，也就是第一个和第一个比，第二个和第二个比……比到一个剩余时间小于当前记录下的距离，也就是过不去了，那么当前的限制时间t偏小，失败。如果全部比完了，都能够走到，那么当前t可以成功控制疫情。 终于说完了.....代码 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,cnt=0; int d[50100]; int head[100100],nxt[100100],to[100100],val[100100]; long long a[50100],f[22][50100],dis[20][50100]; long long tag[50100],rst[50100],q[50100],top[50100]; struct army { int rst,bac; }arr[50100]; bool cmp(int x,int y) { return x>y; } bool cmp1(army x,army y) { return x.rst<y.rst; } bool cmp2(army x,army y) { return x.rst>y.rst; } void addedge(int x,int y,int z) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z; } void dfs(int u,int dep,int t) { d[u]=dep,top[u]=t;//top记录的是当前节点所在的子树除根节点最顶端的节点。也就是相当于用来判断属于根节点的哪棵子树 for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(u==1) t=v; if(!d[v]) dfs(v,dep+1,t),f[0][v]=u,dis[0][v]=val[i]; } } bool can(int x,int fa) { if(tag[x]) return 1; int res=0; for(int i=head[x];i!=-1;i=nxt[i]) { if(to[i]==fa) continue; res++; if(!can(to[i],x)) return 0; } if(!res) return 0; return 1; } bool check(long long t) { int num=0,k=0; memset(tag,0,sizeof(tag)); for(int i=1;i<=m;i++) { long long x=a[i],tmp=t; for(int j=20;j>=0;j--)//倍增爬树 { if(!f[j][x]) continue; if(dis[j][x]>tmp) continue; tmp-=dis[j][x]; if(f[j][x]==1)//如果下一步走到根节点了进行记录并弹出 { arr[++num].rst=tmp,arr[num].bac=top[x]; x=f[j][x]; break; } x=f[j][x]; } tag[x]=1;//tag是记录当前节点有没有被控制 } tag[1]=0;//这个不打会挂光 if(can(1,1)) return 1; sort(arr+1,arr+num+1,cmp1);//排序 for(int i=1;i<=num;i++) if(arr[i].rst<dis[0][arr[i].bac]) if(!can(arr[i].bac,1)) arr[i].rst=-1,tag[arr[i].bac]=1;//不多说已经说了一堆了 sort(arr+1,arr+num+1,cmp2);//再排序 for(int i=head[1];i!=-1;i=nxt[i]) if(!can(to[i],1)) q[++k]=val[i];//记录没根节点到被控制的子树距离 sort(q+1,q+k+1,cmp);//排序 arr[num+1].rst=-0x7fffffff; for(int i=1;i<=k;i++) if(q[i]>arr[i].rst) return 0;//贪心比较 return 1; } int main() { long long l=0,r=0; memset(f,0,sizeof(f)); memset(dis,0,sizeof(dis)); memset(head,-1,sizeof(head)); scanf("%d",&n); int tmp=0; for(int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); addedge(y,x,z); r+=z; if(x==1 || y==1) tmp++; } f[0][1]=0,dfs(1,1,0); for(int i=1;i<=20;i++) for(int j=1;j<=n;j++) { f[i][j]=f[i-1][f[i-1][j]]; dis[i][j]=dis[i-1][j]+dis[i-1][f[i-1][j]]; }//倍增预处理，求出数组 scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&a[i]); if(tmp>m) { printf("-1"); return 0; } while(l<r)//二分答案 { long long mid=(l+r)/2; if(check(mid)) r=mid; else l=mid+1; } printf("%lld",l); return 0; } ```