1946C - Tree Cutting

Problem Link

In this problem, we need to remove k edges from the tree so that the size of the smallest tree created is as large as possible.

We can binary search on the size of the tree, such that every smaller tree created is at least some value. We can run a DFS and find out the minimum number of edges required to split the tree so that each subtree is at least some value. If the number of edges required is more than k, then we can always merge some smaller trees to form larger trees and doing so will still fulfil the size requirement. So, as long as the number of edges required is more than or equal to k for each run of the binary search, we can try increasing the minimum size of the subtree.

Code:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int n, k;

const int maxn = 1e5 + 1;

int st_sz[maxn];

vector <vector <int>> adj;

int used = 0, req = 0;

int dfs(int s, int p) {

    st_sz[s] = 1;

    for (auto i : adj[s]) {

        if (i == p)

            continue;

        st_sz[s] += dfs(i, s);

    }

    if (st_sz[s] >= req) {

        if (s != 1)

            used++;

        return 0;

    }

    if (s == 1 && used == k) {

        used = -1;

    }

    return st_sz[s];

}

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int T;

    cin >> T;

    while (T--) {

        cin >> n >> k;

        adj = vector <vector <int>> (n+1);

        for (int i = 0; i < n-1; i++) {

            int a, b;

            cin >> a >> b;

            adj[a].push_back(b);

            adj[b].push_back(a);

        }

        int lo = 0, hi = n;

        int ans = 1;

        while (lo < hi) {

            int mid = lo + (hi - lo + 1) / 2;

            fill(st_sz, st_sz + n + 1, 0);

            used = 0;

            req = mid;

            dfs(1, 1);

            if (used >= k)

                lo = mid;

            else

                hi = mid - 1;

        }

        cout << lo << '\n';

    }

}