题解 P1084 【疫情控制】

[也许更好的阅读体验 博客园](https://www.cnblogs.com/Morning-Glory/p/11729119.html) [也许更好的阅读体验 CSDN](https://blog.csdn.net/Morning_Glory_JR) # $\mathcal{Description}$ [原题链接](https://www.luogu.org/problem/P1084) **一句话题意** 一个人可以堵住一个子树，不能一次堵住整棵树，求堵住每个通往叶子节点的路径，走的最远的那个人走的路程最少是多少，若不能堵住输出$-1$ # $\mathcal{Solution}$ 看了下其他题解,都说很毒瘤 最开始我也认为很毒瘤 就是在决定一个点是否要跨过根这个地方比较麻烦 但是在码的途中,突然想到一个无脑的方法 于是写起来就很愉快了 最...最..，显然二分路程是多少 再继续想之前，先看一下我们$check$函数要求在什么复杂度决定 $n\leq 50000$，可以$nlog^2n$解决，也就是说$check$的复杂度只要小于$nlogn$即可 一个人在二分到的路程内，尽量往上走是最优的 若一个人可以到达根节点，那么就要考虑其跨过这个根节点去堵其它子树 显然，若跨过根节点，那么走到根节点下面的那个节点就可以了 对于一个可以跨过根节点的人，他可能不要跨过根节点，也可能要跨过根节点 也可能一个子树里的人跨过根节点去堵其他子树，另外的一个子树的人跨过根节点来堵他的子树，这是因为原来这个子树的人比较靠近根节点，跨过根节点后走的较远，而他所在子树与根节点的路径又比较短 想想好像有点麻烦，想到这顿时觉得这题很毒瘤 但其实，我们不用想那么多 我们把所有能跨过根节点的人都走到根节点 将其还允许走的路程全部记下来 把所有需要人去堵的子树找出来，记下其与根节点的距离 显然，能走得最远的人去堵距离根节点最远的子树是最优的 也就是说要从大到小排序，这个过程我们用一个大根堆维护即可 对于一个到子树的距离，我们记下其子树的编号，对于每棵子树，我们记下其内可以跨过根节点的人中，还允许走的路程最少的路程是多少 再考虑一个人可能不要跨过根节点，我们在弹大根堆时，若发现这棵子树可以用比当前允许走的路程最大的人更小的人替代，那么那个人就不需要跨过根节点了 由于那个人仍然在大根堆内，我们把其记在一个队列里，表示有哪些路程被提前用了 这样就是最优的 仍有不懂请看代码，我觉得还是很无脑的，毕竟什么特殊的操作都没有，代码应该一下就看懂了 # $\mathcal{Code}$ ```cpp /******************************* Author:Morning_Glory LANG:C++ Created Time:2019年10月22日 星期二 20时50分59秒 *******************************/ #include <cstdio> #include <fstream> #include <queue> #define ll long long #define inf 12345678987654 #define mp make_pair using namespace std; const int maxn = 500005; const int maxm = 1000006; const int lim = 20; //{{{cin struct IO{ template<typename T> IO & operator>>(T&res){ res=0; bool flag=false; char ch; while((ch=getchar())>'9'||ch<'0') flag|=ch=='-'; while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar(); if (flag) res=~res+1; return *this; } }cin; //}}} int n,m,cnt,u,v,val,num; int head[maxn],nxt[maxm],to[maxm],w[maxm],hav[maxn],dep[maxn],lg[maxn]={-1}; int fa[maxn][lim]; ll l,r,mid; ll d[maxn],f[maxn]; bool vis[maxn]; priority_queue <int> qc,qf; priority_queue < pair<int,int> >qn; //{{{add void add (int u,int v,int val) { nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,w[cnt]=val; } //}}} //{{{dis ll dis (int x,int y) { return d[x]>d[y]?d[x]-d[y]:d[y]-d[x]; } //}}} //{{{dfs void dfs (int x) { r=max(r,d[x]); for (int i=1;i<=lg[dep[x]];++i) fa[x][i]=fa[fa[x][i-1]][i-1]; for (int e=head[x];e;e=nxt[e]) if (to[e]!=fa[x][0]){ fa[to[e]][0]=x,dep[to[e]]=dep[x]+1; d[to[e]]=d[x]+w[e]; dfs(to[e]); } } //}}} //{{{move void move (int x,int nm) { ll t=mid; for (int i=lg[dep[x]];~i;--i){ ll ds=dis(fa[x][i],x); if (fa[x][i]>1&&t>=ds) t-=ds,x=fa[x][i]; } if (t>dis(1,x)){ ll ds=t-dis(1,x); f[x]=min(f[x],ds); while (nm--) qc.push(ds); } else vis[x]=true; } //}}} //{{{chk bool chk (int x) { if (vis[x]) return false; bool flag=true; for (int e=head[x];e;e=nxt[e]) if (to[e]!=fa[x][0]){ flag=false; if (chk(to[e])) return true; } return flag; } //}}} //{{{check bool check () { while (!qc.empty()) qc.pop(); while (!qn.empty()) qn.pop(); while (!qf.empty()) qf.pop(); for (int i=1;i<=n;++i) vis[i]=0,f[i]=inf; for (int i=1;i<=n;++i) if (hav[i]) move(i,hav[i]); for (int e=head[1];e;e=nxt[e]) if (chk(to[e])) qn.push(mp(w[e],to[e])); while (!qn.empty()){ val=qn.top().first,v=qn.top().second,qn.pop(); while (!qf.empty()&&qf.top()==qc.top()) qf.pop(),qc.pop(); if (qc.empty()) return false; if (qc.top()<val){ if (f[v]>qc.top()) return false; qf.push(f[v]); } else if (f[v]<=qc.top()) qf.push(f[v]); else qc.pop(); } return true; } //}}} int main() { cin>>n; for (int i=1;i<=n;++i) lg[i]=lg[i>>1]+1; for (int i=2;i<=n;++i){ cin>>u>>v>>val; if (u==1||v==1) ++num; add(u,v,val),add(v,u,val); } cin>>m; if (m<num) return printf("-1\n"),0; for (int i=1;i<=m;++i) cin>>u,++hav[u]; dfs(1); r<<=1; while (l<r){ mid=(l+r)/2; if (check()) r=mid; else l=mid+1; } printf("%lld\n",l); return 0; } ``` >如有哪里讲得不是很明白或是有错误，欢迎指正