开学大二补题（第二周）

这几天比赛发现短板很明显，写题异常慢，但是题是可以写出来的

还有就是wa的太随便动不动就是一个很简单的点给我wa了

总之，题刷少了

Problem - H - Codeforces

题意：就是给你一个棵树，这棵树分很多的叶子 一共n个点   然后让你对这个树进行层减

一共减k层 就是一层一层的去掉，然后输出还剩点的个数

题解：这道题就是一个拓扑排序的题

很好想，一层一层搞我们发现就和这些点的边数有关边数少的绝对最最低层

所以我们可以记录每一个点连起来的边数只要出度为1那么这个点就是最底层的点我们就删除即可

然后跑一个广搜    这样的首先记录现在就是1的底层点如何入队就可以了

跑队列的时候就用这些1的点因为底层的点被我们剪掉了，所以边也没了，和这些底层相连的点边数就要减减，然后减完看看这个点是不是边数只有1了

如果是那么然后减的层数不够，这点就入队，够就不入队，就行了

#include <bits/stdc++.h>
#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=1e6+5,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;
int bian[N];

int n1,k1;
int dep[N];
vector<int> a[N];
int su;
void bfs(int n,int k)
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(bian[i]==1)
        {
            q.push(i);
            bian[i]=0;
            su++;
            dep[i]=1;
        }
    }
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for(auto x:a[u])
        {
            bian[x]--;
            if(bian[x]==1 && dep[u]<k)
            {
                su++;
                q.push(x);
                dep[x]=dep[u]+1;
            }
        }
    }
}
void solve() {

    cin>>n1>>k1;
    for(int i=1;i<=n1;i++) bian[i]=0, dep[i]=1, a[i].clear();
    su=0;
    for(int i=1;i<n1;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
        bian[x]++;
        bian[y]++;
    }
    if(n1==1 || 2*k1>=n1)
    {
        cout<<0<<endl;
        return;
    }
        bfs(n1,k1);
        cout<<n1-su<<endl;



}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}