【CF 510 F】Leaf Set

題目連結

題意

給定一棵樹,要求把葉子節點分成最少的集合,使得集合内點對兩兩距離不超過K

Sol

套路: 要求點對間兩兩距離不超過K,等價于在每條邊上建立一個點,然後找到一個點使得它到所有集合内的點的距離不超過K

這樣轉化完就變成了選取最少的點覆寫所有的葉子,就是個很裸的貪心了 (然而打比賽的時候并沒有看出來TAT)

正确性:

對于本來的一條長度為 L 的路徑,把邊拆成點後必然路徑長度變為 2L , 那麼隻要點集内所有的點都能到達你選的點,他們到達彼此的距離就小于等于 2K , 在原圖中就會 小于等于 K , 這樣就證明了正确性

代碼:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
const int N=2e6+10;
inline int read()
{
	char ch=getchar();int t=1;int x=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	return x*t;
}
struct edge{
	int to,next;
}a[N<<1];
int head[N];int cnt=0;
int K;
int n;
const int INF=1e9;
inline void add(int x,int y){a[++cnt]=(edge){y,head[x]};head[x]=cnt;}
int near[N],away[N];
int du[N];
int ans=0;
void dfs(int u,int fa)
{
	near[u]=INF;away[u]=-INF;
	for(register int v,i=head[u];i;i=a[i].next)
	{
		v=a[i].to;if(v==fa) continue;
		dfs(v,u);near[u]=min(near[v]+1,near[u]);
		if(near[v]+away[v]>K) away[u]=max(away[u],away[v]+1);
	}
	if(fa) {if(away[u]>=K) ++ans,away[u]=-INF,near[u]=0; else if(du[u]==1) away[u]=0;}
	else {
		if(du[u]==1) away[u]=max(away[u],0);
		if(near[u]+away[u]>K) ++ans;
	}
	return;
}
int main()
{
	n=read();K=read();register int u,v;
	for(register int i=n-1;i;--i){
		u=read();v=read();++n;
		add(u,n);add(n,u);add(v,n);add(n,v);++du[u];++du[v];
	}
	dfs(1,0);
	printf("%d\n",ans);
}