Code : Tree Cutting

#include <bits/stdc++.h>
using namespace std;

class Tree {
  public:
    int n;
    vector<vector<int>> adj;
    int cut, min_cc_size;
    vector<int> mega;
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        mega.resize(n);
    }

    void dfs(int src, int par) {
        mega[src] = 1;
        for (auto &child : adj[src]) {
            if (child == par) {
                continue;
            }
            dfs(child, src);
            if (mega[child] < min_cc_size) {
                mega[src] += mega[child];
            } else {
                cut++;
            }
        }
    }

    bool ok(int k) { return (cut == k && mega[0] >= min_cc_size) || cut > k; }

    void reset(int mid) {
        cut = 0;
        min_cc_size = mid;
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    Tree t(n);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        t.adj[x].push_back(y);
        t.adj[y].push_back(x);
    }

    int low = 0, high = n, res = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        t.reset(mid);
        t.dfs(0, -1);
        if (t.ok(k)) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << res << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        solve();
    }
    return 0;
}