OI - DYN-Dynamite(洛谷) | Lucky_Glass's Blog
0%

OI - DYN-Dynamite(洛谷)

洛谷的题意还不如直接看英文……


# 题面

> Linked 洛谷 P3523

点击展开/折叠题面

有一棵 $n$ 个节点的树,树上有一些点是关键点,记关键点集合为 $\mathbb A$;你需要选择树上恰好 $m$ 个不同点,记为点集 $\mathbb B$,最小化下面的式子:

$$ \max_{u\in\mathbb A}\Big\{\min_{v\in\mathbb B}\{\text{dist}(u,v)\}\Big\} $$

$n\le 3\times10^5$


# 解析

要求最大值最小,容易想到二分答案。

假设我们二分出的答案是 $d$,这就意味着——任何一个关键点周围距离 $d$ 范围内至少有一个你选择的点。

于是检验 $d$ 是否合法,只需检验“使得每个关键点距离 $d$ 以内都有选择点”的最少选择点个数是否小于 $m$。

那么问题就是怎么求最小需要选多少个点。由于是树形结构,点的深度在一定程度上可以代表距离,不妨贪心地想——

不到deadline不工作, 那么不到必须放置选择点就不放置。

做一遍 DFS,维护 select[u]deepkey[u] 分别表示 $u$ 子树内选择点与 $u$ 的父节点的最小距离、$u$ 子树内的还需要选择点的关键点与 $u$ 的父节点的最大距离;已经决策了 $u$ 子树内哪些点是选择点,并且保证此时 $u$ 子树内的所有关键点都还有可能满足条件。

为什么这样维护?因为 $u$ 子树内还没有已经不合法的关键点,那么选择点越靠上,越有可能给 $u$ 子树外的关键点提供贡献;而 $u$ 子树内还需要选择点的关键点越深,就越有可能不合法。

$u$ 子树中没有选择点时,$select_u=+\infty$;$u$ 子树中没有关键点时,$deepkey_u=-1$。

记 $v$ 是 $u$ 的子节点,$S=\min\{select_v\},D=\{\max\{deepkey_v\}$(若 $u$ 本身是关键点,$D$ 与 $0$ 取 max),如果我们发现:

  • $S+D\le d$,那么 $u$ 子树中原有的选择点就已经能够满足 $u$ 中的所有关键点,则 $u$ 本身并不需要被选择

  • $S+D>d$ 且 $D=d$,说明 $u$ 子树中有关键点没有满足,并且如果不选择 $u$,这个关键点就已经不合法了,因此必须选择 $u$,那么此时 $u$ 子树的所有关键点被满足:

  • $D\neq -1$ 且 $u$ 是DFS的根节点,$u$ 必须设为选择点;
  • 其余情况

这样一遍 $O(n)$ 的 DFS 就可以求出最少需要多少关键点。结合二分可以 $O(n\log n)$ 解决本题。


# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3e5+10;
#define ci const int &

struct GRAPH{
int head[N],to[N<<1],nxt[N<<1],ncnt;
void AddEdge(ci u,ci v){
int p=++ncnt,q=++ncnt;
to[p]=v,nxt[p]=head[u],head[u]=p;
to[q]=u,nxt[q]=head[v],head[v]=q;
}
inline int operator [](ci u){return head[u];}
}Gr;

int n,m,ned;
bool key[N];
int depkey[N],slc[N];

void DFS(ci u,ci fa,ci dis){
slc[u]=n,depkey[u]=key[u]==true? 0:-1;
for(int it=Gr[u];it;it=Gr.nxt[it]){
int v=Gr.to[it];
if(v==fa) continue;
DFS(v,u,dis);
slc[u]=min(slc[u],slc[v]);
depkey[u]=max(depkey[u],depkey[v]);
}
if(slc[u]+depkey[u]<=dis) depkey[u]=-1,slc[u]++;
else if(depkey[u]==dis || ((~depkey[u]) && !fa)) slc[u]=1,depkey[u]=-1,ned++;//select u
else{
if(~depkey[u]) depkey[u]++;
slc[u]++;
}
}
bool Check(int dis){
ned=0;
DFS(1,0,dis);
return ned<=m;
}
int main(){
// freopen("input.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&key[i]);
for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),Gr.AddEdge(u,v);
int lef=0,rig=n;
while(lef+1<rig){
int mid=(lef+rig)>>1;
if(Check(mid)) rig=mid;
else lef=mid;
}
printf("%d\n",Check(lef)? lef:rig);
return 0;
}

THE END

Thanks for reading!

> Linked 你别忘-网易云