前置知识
解法
答案显然具有单调性，考虑二分答案。
设当前二分出的答案为 \(mid\)，则等价于覆盖距离为 \(mid\) 的情况下进行选点。
做法同 luogu P3942 将军令 ，考虑进行贪心，对于深度最深的叶节点将选择的点放在边界时，即取 \(mid\) 级祖先时，覆盖的范围一定最大。
设 \(f_{x}\) 表示 \(x\) 到以 \(x\) 为根的子树内最远的没被覆盖的点的距离，\(g_{x}\) 表示 \(x\) 到以 \(x\) 为根的子树内最近被选的点的距离，状态转移方程为 \(\begin{cases} f_{x}=\max\limits_{y \in Son(x)}\{ f_{y}+1 \} \\ g_{x}=\min\limits_{y \in Son(x)}\{ g_{y}+1 \}\end{cases}\)，
当 \(g_{x}>mid\) 时以 \(x\) 为根的子树内所选的点覆盖不到自己，需要祖先节点进行覆盖，此时需要统计自己的贡献，即 \(f_{x}=\max(f_{x},0)\)；当 \(f_{x}+g_{x} \le mid\) 时以 \(x\) 为根的子树内所选的点就能覆盖整棵子树，令 \(f_{x}=- \infty\)；当 \(f_{x}=mid\) 说明 \(x\) 必须被选，令 \(f_{x}=- \infty,g_{x}=0\)，选择点数加一。
特判下根节点没有被覆盖的情况。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct node
{
int nxt,to;
}e[400010];
int head[400010],f[400010],g[400010],cnt=0,sum=0;
void add(int u,int v)
{
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs(int x,int fa,int k)
{
f[x]=-0x3f3f3f3f;
g[x]=0x3f3f3f3f;
for(int i=head[x];i!=0;i=e[i].nxt)
{
if(e[i].to!=fa)
{
dfs(e[i].to,x,k);
f[x]=max(f[x],f[e[i].to]+1);
g[x]=min(g[x],g[e[i].to]+1);
}
}
if(g[x]>k)
{
f[x]=max(f[x],0);
}
if(f[x]+g[x]<=k)
{
f[x]=-0x3f3f3f3f;
}
if(f[x]==k)
{
f[x]=-0x3f3f3f3f;
g[x]=0;
sum++;
}
}
bool check(int mid,int k)
{
sum=0;
dfs(1,0,mid);
sum+=(f[1]>=0);
return sum<=k;
}
int main()
{
int n,k,u,v,l=0,r,mid,ans=0,i;
cin>>n>>k;
r=n;
for(i=1;i<=n-1;i++)
{
cin>>u>>v;
add(u,v);
add(v,u);
}
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,k)==true)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
cout<<ans<<endl;
return 0;
}
后记
多倍经验：luogu P3942 将军令 | luogu P2279 [HNOI2003] 消防局的设立 | luogu P2899 [USACO08JAN] Cell Phone Network G | UVA1218 完美的服务 Perfect Service | luogu P3523 [POI2011] DYN-Dynamite
标签：Information,ARC116E,子树内,int,题解,cnt,mid,为根,luogu From： https://www.cnblogs.com/The-Shadow-Dragon/p/18323198