Expert.
Put your skills to the test.

Problem summary

N unit-time operations form a tree directed from children to their parent. An operation starts only after all its children finish. Schedule at most M ready operations each tick, always choosing the deepest ready vertices, and output the minimum makespan. The statement supplies the optimality theorem for this level policy.

Constraints

1 ≤ N,M ≤ 100000.

Worked example

Official sample; other valid outputs may exist.

14 3
1 3
2 3
3 4
7 4
4 5
5 6
10 11
9 11
8 11
11 5
12 13
13 6
14 6

6

Solution analysis

1. Find the root as the only vertex without a parent. Traverse outward from it to compute depths, and count each vertex’s unfinished children. Initially only leaves are ready.
2. A maximum priority queue orders ready operations by depth. At each tick remove up to M vertices into a separate batch; only after selecting the whole batch decrement their parents’ unfinished-child counters. Newly ready parents enter the heap for the next tick.
3. For the sample, three operations run during each of the first four ticks. The final two operations form the chain 5→6 and need two more ticks, yielding 6.

Why it works

Initially the heap consists exactly of ready leaves. After each complete tick, decrementing counters makes a parent ready exactly when its last child finishes. Therefore each batch is a legal batch of the deepest ready operations. The algorithm implements the level schedule that the statement guarantees has minimum duration.

Watch out. Do not insert and execute a parent in the same tick as its child. Avoid recursive DFS on a 100000-vertex chain.

An independently written complete program with standard headers.

// Key idea: Initially the heap consists exactly of ready leaves. After each complete tick,
// decrementing counters makes a parent ready exactly when its last child finishes.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>parent(n,-1),remaining(n),depth(n);
    vector<vector<int>>children(n);
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        --u;
        --v;
        parent[u]=v;
        children[v].push_back(u);
        ++remaining[v];
    }
    int root=0;
    while(parent[root]!=-1){
        root=parent[root];
    }
    vector<int>order(1,root);
    for(size_t i=0;i<order.size();++i){
        for(int v:children[order[i]]){
            depth[v]=depth[order[i]]+1;
            order.push_back(v);
        }
    }
    priority_queue<pair<int,int>>ready;
    for(int i=0;i<n;++i){
        if(remaining[i]==0){
            ready.push({depth[i],i});
        }
    }
    int ticks=0;
    while(!ready.empty()){
        vector<int>batch;
        int count=min(m,static_cast<int>(ready.size()));
        for(int i=0;i<count;++i){
            batch.push_back(ready.top().second);
            ready.pop();
        }
        for(int u:batch){
            int p=parent[u];
            if(p!=-1&&--remaining[p]==0){
                ready.push({depth[p],p});
            }
        }
        ++ticks;
    }
    cout<<ticks<<'\n';
}