做法:先将度数小于等于 1 的点加入队列,作为第一层(第一次删除就被删掉的点),然后 bfs 层层扩展,最后统计,但是 WA 了,求助大佬orz
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN=4e5+10;
int T;
int n, k, d[MAXN], s[MAXN], t[MAXN], e[MAXN], maxs, ans;
vector <int> g[MAXN];
void bfs()
{
queue <int> q;
bool vis[MAXN]={0};
maxs=1;
for(int i=1; i<=n; i++)
if(d[i]<=1)
{
vis[i]=1, s[i]=1, e[1]++;
q.push(i);
}
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=1, s[v]=s[u]+1, e[s[v]]++, maxs=max(maxs, s[v]);
q.push(v);
}
}
}
}
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &k);
memset(d, 0, sizeof(d));
memset(s, 0, sizeof(s));
memset(t, 0, sizeof(t));
memset(e, 0, sizeof(e));
for(int i=1; i<=n; i++)
g[i].clear();
for(int i=1; i<=n-1; i++)
{
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
d[u]++, d[v]++;
}
bfs();
ans=n;
for(int i=1; i<=min(maxs, k); i++)
ans-=e[i];
printf("%d\n", ans);
}
return 0;
}