在暴力的时候我们每轮都要查询每个点的度数，但其中很多点的度数其实并没有改变，所以我们考虑每轮只访问度数改变的节点。

在最开始时，将所有度数为 $k$ 的节点取出，可以用队列等方式存储。

接下来每一轮，我们只需在删除点时，枚举每条和这个点相连的边，并将边的另一端的点度数减一，而当另一端的点度数恰好减为$k$时，就将其加入一个新的队列，表示这个点可能在下一轮被删除。

在本轮删点结束后，所有新队列中的点就可能在下一轮中被删除，但也可能在本轮中度数被减到小于 $k$ 。所以只需再扫一遍新队列，把现在度数仍为 $k$ 的点取出，即为下一轮所需要删除的点。

考虑这样的复杂度，首先对于一棵n个点的树，其每个点的度数之和为 $2(n −1)$ 而我们的删点操作，对于单点来说其复杂度为这个点的度数

所以删去所有点的复杂度最多为$O(n)$。 而每个点最多进入一次‘新队列’，故我们遍历新队列检验每个点是否需 要被删的复杂度也是$O(n)$。 故总复杂度可以做到$O(n)$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PB push_back
#define fr(i, a, b) for (int i = (int)a; i <= (int)b; i++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
vector<int> edge[1000005];
int vis[1000005];
int d[1000005] ;
void dfs(int u)
{
    for (auto v : edge[u])
    {
        if (!vis[v])
        {
            vis[v] = 1;
            dfs(v);
        }
    }
}
void slove()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
    	int x,y;
        cin >> x >> y;
        edge[x].PB(y);
        edge[y].PB(x);
        d[x]++;
        d[y]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (d[i] == k)
        {
        	vis[i] = 1;
            q.push(i);
        }
    }
    queue<int> q2;
    while (1)
    {
        if (q.empty())
        {
            if (q2.empty())
                break;
            while (!q2.empty())
            {
                int u = q2.front();
                q2.pop();
                if (d[u] == k)
                {
                    q.push(u);
                }
            }
            if(q.empty()) break;
        }
        int u = q.front();
        q.pop();
        vis[u] = 1;
        for (auto v : edge[u])
        {
            if (--d[v] == k)
            {
                q2.push(v);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            ans++;
            dfs(i);
        }
    }
    cout << ans << endl;
}
signed main()
{
    int tcase = 1;
    while (tcase--)
    {
        slove();
    }
    return 0;
}