Daily Problem | CF1946C – Binary Search, DP, Tree Structure

Problem Summary

Given a tree with nodes, we need to delete exactly edges such that the number of nodes in all connected components after deletion is **at least **.

The goal is to find the maximum integer that satisfies this condition.

Solution Approach

This problem is a typical case of “tree partitioning + binary search on the answer”.

We want to find the largest such that we can partition into at least connected components, each with a node count ≥ .

1️⃣ Binary Search on the Answer

We perform a binary search on the value of :

• Lower bound (the minimum possible block size is 1);
• Upper bound (the maximum possible block size is the entire tree).

For a midpoint value , we need to verify if we can partition into components that satisfy each block ≥ .

Thus, we design the <span>check(x)</span> function for validation.

2️⃣ Core Logic — DFS Divide and Conquer Counting

<span>check(x)</span> is tasked with:

Determining whether it is possible to partition into at least blocks with each block size ≥ .

Using DFS starting from the root node (arbitrarily chosen as 1), we count the number of nodes in each subtree:

• <span>siz[u]</span> represents the number of nodes in the subtree rooted at the current node that have not been separated into blocks;
• For each child node :
• Recursively calculate its subtree;
• If <span>siz[v] >= x</span>, it indicates that this subtree can be an independent block, we can cut this edge to form a block, → block count <span>sum++</span>, and subtract the node count of this subtree from the current count;
• Otherwise, the part of the subtree that does not meet the requirement is merged into the parent node,<span>siz[u] += siz[v]</span>.

After the entire DFS ends:

• If the remaining part (<span>cnt >= x</span>) can still form a block,<span>sum++</span>;
• Check if the final block count <span>sum >= k+1</span> holds true.

3️⃣ Check Function Combined with Binary Search

If <span>check(x)</span> is true, it indicates that we can at least partition into valid blocks, then we continue to try larger (increase the lower bound); otherwise, it indicates that the blocks are too large to meet the requirements, so we decrease (reduce the upper bound).

The final upper bound of the binary search <span>l</span> is the maximum feasible .

Reference Code

#include<bits/stdc++.h>
using namespace std;
int n, k, sum, siz[100005], cnt;
vector<int> e[100005];

// DFS: Determine how many blocks can be formed under the current partition
void dfs(int u, int fa, int w){
    siz[u] = 1;
    for (int v : e[u]){
        if (v == fa) continue;
        dfs(v, u, w);
        if (siz[v] >= w) sum++, cnt -= siz[v]; // Subtree can be an independent block
        else siz[u] += siz[v];                 // Otherwise merge into parent node
    }
}

// Check if we can partition into >= k+1 blocks of size ≥ x
bool check(int x){
    sum = 0; cnt = n;
    fill(siz + 1, siz + n + 1, 0);
    dfs(1, 0, x);
    if (cnt >= x) sum++;  // If remaining nodes can still form a block
    return sum >= k + 1;
}

// Main logic: Binary search on the answer
void solve(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++) e[i].clear();
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int l = 1, r = n;
    while (l < r){
        int mid = (l + r + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}

int main(){
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

🔍 Algorithm Complexity Analysis

Step	Complexity
Each <span>check(x)</span>	(one DFS)
Number of binary searches
Total complexity
Space complexity