目录
Description
有一棵树,每次操作将叶子节点或根节点删除掉, \(k\) 此操作之后会剩下多少节点
State
\(1<=t<=10^4\)
\(1<=n<=4*10^5\)
\(1<=k<=2*10^5\)
Input
6
14 1
1 2
2 3
2 4
4 5
4 6
2 7
7 8
8 9
8 10
3 11
3 12
1 13
13 14
2 200000
1 2
3 2
1 2
2 3
5 1
5 1
3 2
2 1
5 4
6 2
5 1
2 5
5 6
4 2
3 4
7 1
4 3
5 1
1 3
6 1
1 7
2 1
Output
7
0
0
3
1
2
Solution
思路是拓扑排序很容易知道,无向图中要避免一个节点放入重复放入队列(需要严格控制进队列的条件或 \(vis\) 数组判断)
$hint: $ 当只有一个节点的时候,答案应该是 \(0\)
Code
const int N = 4e5 + 5;
int n, m, k, _;
int a[N];
vector<int> v[N];
int into[N];
int vis[N];
void init()
{
for(int i = 1; i <= n; i ++){
v[i].clear();
into[i] = 0;
vis[i] = 0;
}
}
signed main()
{
// IOS;
rush(){
sdd(n, m);
int x, y;
init();
rep(i, 1, n - 1){
sdd(x, y);
v[x].pb(y);
v[y].pb(x);
into[x] ++;
into[y] ++;
}
if(n == 1){
pd(0);
continue;
}
int ans = n;
queue<int> q;
for(int i = 1; i <= n; i ++){
if(into[i] == 1){
q.push(i);
vis[i] = 1;
}
}
while(m --> 0 && ans){
int sz = q.size();
while(sz --> 0){
int u = q.front();
q.pop();
ans --;
for(auto it : v[u]){
if(vis[it]) continue;
into[it] --;
if(into[it] == 1){
q.push(it);
vis[it] = 1;
}
}
}
}
pd(ans);
}
// PAUSE;
return 0;
}