CF1593E-Gardener-and-Tree-题解

title: CF1593E Gardener and Tree 题解
date: 2022-05-27 21:30:48
categories: 
 - 题解

原题面

题意：

给出一个 \(n\) 个点的树，删除 \(k\) 次叶子节点，求剩下的节点数。

思路：

设 \(cnt_i\) 为 \(k\) 最小为多少时点 \(i\) 会被删除。

当 \(i\) 将要被删除时，它一定是现在的叶子，联想到拓扑排序的特点，直接跑一遍拓扑排序即可。

初始时所有叶子的 \(cnt\) 都为 \(1\)，跑完拓扑排序后遍历一遍 \(cnt\) 数组统计 \(cnt_i > k\) 的数量，时间复杂度 \(O(n)\)。

code：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=4e5+10;
int t,n,k,cnt[N],d[N],ans;
bool f[N];
vector<int> g[N];
queue<int> q;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		ans=0;
		memset(f,0,sizeof(f));
		memset(d,0,sizeof(d));
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)g[i].clear();
		for(int i=1,x,y;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			g[x].push_back(y);
			g[y].push_back(x);
			d[x]++,d[y]++;
		}
		if(k==0)
		{
			printf("%d\n",n);
			continue;
		}
		for(int i=1;i<=n;i++)if(d[i]==1)q.push(i),f[i]=cnt[i]=1;
		while(!q.empty())
		{
			int t=q.front(); 
			q.pop();
			for(int i=0;i<g[t].size();i++)
			{
				int v=g[t][i];
				if(f[v])continue;
				d[v]--;
				if(d[v]==1)
				{
					f[v]=1;
					cnt[v]=cnt[t]+1;
					q.push(v);
				}
			}
		}
		for(int i=1;i<=n;i++)if(cnt[i]>k)ans++;
		printf("%d\n",ans);
	}
}