NOIP2012 疫情控制[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

也许更好的阅读体验

$\mathcal{Description}$
原题链接

set
一句话题意
一个人可以堵住一个子树，不能一次堵住整棵树，求堵住每个通往叶子节点的路径，走的最远的那个人走的路程最少是多少，若不能堵住输出 $- 1$

$\mathcal{Solution}$
看了下其他题解,都说很毒瘤
最开始我也认为很毒瘤
就是在决定一个点是否要跨过根这个地方比较麻烦
但是在码的途中,突然想到一个无脑的方法
于是写起来就很愉快了

最…最…，显然二分路程是多少

再继续想之前，先看一下我们 $c h e c k$ 函数要求在什么复杂度决定
$n\leq 50000$ ，可以 $nlog^2n$ 解决，也就是说 $c h e c k$ 的复杂度只要小于 $n l o g n$ 即可

一个人在二分到的路程内，尽量往上走是最优的
若一个人可以到达根节点，那么就要考虑其跨过这个根节点去堵其它子树
显然，若跨过根节点，那么走到根节点下面的那个节点就可以了

对于一个可以跨过根节点的人，他可能不要跨过根节点，也可能要跨过根节点
也可能一个子树里的人跨过根节点去堵其他子树，另外的一个子树的人跨过根节点来堵他的子树，这是因为原来这个子树的人比较靠近根节点，跨过根节点后走的较远，而他所在子树与根节点的路径又比较短
想想好像有点麻烦，想到这顿时觉得这题很毒瘤

但其实，我们不用想那么多
我们把所有能跨过根节点的人都走到根节点
将其还允许走的路程全部记下来
把所有需要人去堵的子树找出来，记下其与根节点的距离
显然，能走得最远的人去堵距离根节点最远的子树是最优的

也就是说要从大到小排序，这个过程我们用一个大根堆维护即可
对于一个到子树的距离，我们记下其子树的编号，对于每棵子树，我们记下其内可以跨过根节点的人中，还允许走的路程最少的路程是多少

再考虑一个人可能不要跨过根节点，我们在弹大根堆时，若发现这棵子树可以用比当前允许走的路程最大的人更小的人替代，那么那个人就不需要跨过根节点了
由于那个人仍然在大根堆内，我们把其记在一个队列里，表示有哪些路程被提前用了
这样就是最优的
仍有不懂请看代码，我觉得还是很无脑的，毕竟什么特殊的操作都没有，代码应该一下就看懂了

$\mathcal{Code}$

/******************************* 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;
}