自动搬运

查看原文

来自洛谷，原作者为

	Reply_ 我恨快速幂

搬运于2025-08-24 23:17:11，当前版本为作者最后更新于2025-06-01 13:59:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

树上问题，贪心解决。

题面告诉我们每一条长度大于等于 $k$ 的路径上都必须要有一座加油站。

对于树上的关于路径的问题，我们对于路径两端点的 $\operatorname{LCA}$ 考虑。

处于贪心的思想，对于一个点而言，我们会在不得不建加油站的时候建立加油站，怎么判断一个点是不得不建加油站呢，就是这个点的子树内有一条没有建立过加油站的路径，其长度大于等于 $k$ 的时候，我们不得不建加油站。

为什么这个贪心是对的，也很显然，我们希望一个加油站能影响更多的路径，所以应越靠近根节点越好，所以应当这么做。

实现

定义 $sum_i$ 代表以 $i$ 为根的子树中离 $i$ 最远的点距离 $i$ 的距离，但是这个点到 $i$ 的路径上不能有加油站建立过。

这样对于枚举到的 $u$，如果有两棵子树的 $sum$ 的和加 $2$ 大于等于 $k$ 那么就要建加油站（或者某一棵子树连到 $u$ 的时候直接就超过 $k$ 了，也要建）。

注意：如果决定要建加油站，那么把 $sum$ 赋值为 $-1$，这样向上传递的时候才不会出错（其父节点的 $sum$ 为零）。

代码

#include<bits/stdc++.h>
#define ll long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=2e5+10;
int n,k;
vector<int>g[N];
void add(int ui,int vi)
{
	g[ui].push_back(vi);
	return;
}
int sum[N];//以i为根的子树中离i最远的未被覆盖的点距离i的距离
void dfs(int u,int fa)
{
	sum[u]=0;
	for(int i = 0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa) continue;
		dfs(v,u);
		sum[u]=max(sum[u],sum[v]+1);
	}
	int maxn=-1e9;
	for(int i = 0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa) continue;
		if(sum[v]+1>=k){
			vis[u]=1;
			sum[u]=-1;
			break;
		}
		if(maxn+2+sum[v]>=k){
			vis[u]=1;
			sum[u]=-1;
			break;
		}
		maxn=max(sum[v],maxn);	
	}
	return;
}
signed main()
{
	n=read(),k=read();
	F(i,1,n-1){
		int ui=read(),vi=read();
		add(ui,vi);
		add(vi,ui);
	}
	dfs(1,0);
	int sum=0;
	for(int i = 1;i<=n;i++){
		sum+=vis[i];
	}
	cout << sum << '\n';
	return 0;
}
/*

*/