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);
}
}