\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Ta ưu tiên xóa những đỉnh xa so với gốc nhất (độ sâu lớn nhất), và trong những đỉnh cùng độ sâu ta ưu tiên đỉnh mà cha của nó ít con hơn

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Đâu tiên chúng ta tìm rễ của cây, \(dfs()\) xuống ta sẽ tính được độ sâu của các đỉnh

• Sau đó chúng ta sẽ tỉa từ lá cây lên rễ, ưu tiên tỉa những đỉnh có độ sâu lớn hơn.

• Khi tỉa một đỉnh, thì số đỉnh con trong cha nó sẽ giảm, khi không còn đỉnh con thì thêm đỉnh cha vào

\(\color{brown}{\text{Giải thích code}}\)

• Khởi tạo tất cả đỉnh \(u\) có cha là \(par[u] = 0\)

Khi thêm cạnh \(u \rightarrow v\), ta gán \(par[u] = v\)

Sau khi thêm các cạnh, ta tìm rễ bằng cách chọn ngẫu nhiên đỉnh bắt đầu và gọi nó là \(root\).

Trong khi \(par[root] \neq 0\) thì ta gán \(root = par[root]\).

• Khởi tạo các đỉnh \(u\) có các đỉnh con là tập \(G[u]\), số đỉnh con là \(cnt[u]\)

Khi ta thêm canh \(u \rightarrow v\) thì ta thêm \(u\) vào \(G[v]\)

Để cho tiện, sau khi ta thêm các cạnh ta duyệt qua các \(u\) và gán \(cnt[u] = |G[u]|\)

• Khởi tạo rễ \(root\) có độ sau là \(depth[root] = 0\)

Sau đó ta \(dfs(u)\) từ \(root\) xuống

Duyệt các đỉnh con \(v \in G[u]\), ta gán \(depth[v] = depth[u] + 1\) và tiếp tục \(dfs(v)\)

• Để xử lí, ta sẽ tạo heap \(S\) ưu tiên các đỉnh có độ sau lớn hơn, khởi tạo gồm các lá của cây

• Mỗi vòng lặp mà \(S\) vẫn con đỉnh, ta tăng biến đếm \(res\) (khởi tạo \(0\)), ngược lại ta dừng chương tình và xuất \(res\)

Tạo tập các đỉnh sẽ bị mất đi một con là \(V\)

Duyệt qua \(k\) phần tử hoặc khi \(S\) rỗng, ta thêm đỉnh \(par[S.top]\) vào \(V\)

Sau đó ta duyệt các đỉnh \(v \in V\), giảm số lượng đỉnh con \(cnt[v] = cnt[v] - 1\), và nếu hết đỉnh con \((cnt[v] = 0)\) thì ta thêm đỉnh \(v\) vào \(S\)

\(\color{purple}{\text{Độ phức tạp}}\)

\(\color{green}{\text{Code tham khảo }}\): Đồ thị, Cấu trúc dữ liệu đặc biệt (Heap), Tham lam

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n log n)\ \color{purple}{\text{thời gian}}\ ||\ O(n log n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

#define heap priority_queue
#define FASTIO ios::sync_with_stdio(NULL), cin.tie(NULL);

typedef pair<int, int> ii;
const int LIM = 300300;

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, m, k;
int cnt[LIM];
int par[LIM];
int depth[LIM];
vector<int> G[LIM];
int input()
{
    memset(par, 0, sizeof(par));
    cin >> n >> k;
    m = n - 1;

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        par[u] = v;
        G[v].push_back(u);
    }
}

void dfs(int u)
{
    for (int v : G[u])
    {
        depth[v] = depth[u] + 1;
        dfs(v);
    }
}

int solve()
{
    int root = 1;
    /// find root that par[root] = 0
    while (par[root]) root = par[root];
    memset(depth, 0, sizeof(depth));
    depth[root] = 0;
    dfs(root);

    heap<ii> S;
    for (int u = 1; u <= n; ++u) 
    {
        cnt[u] = G[u].size();
        if (G[u].empty()) /// Leaf
        {
            S.push(ii(depth[u], u));
        }
    }

    int time = 0;
    while (S.size())
    {
        ++time;
        vector<int> nxt;
        for (int i = 0; S.size() && i < k; ++i)
        {
            int u = S.top().second;
            nxt.push_back(par[u]);
            S.pop();
        }

        for (int v : nxt)
        {
            if (--cnt[v] == 0) /// Next to be free
            {
                S.push(ii(depth[v], v));
            }
        }
    }

    cout << time;
}

int main()
{
    FASTIO;
    input();
    solve();
    return 0;
}