fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<long long , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const long long INF = 1e16;
  21. const int N = 3e5 + 7;
  22. int n , m;
  23. vector<int> a[N] , adj[N];
  24. int col[N] , cnt[N] , topo[N] , p = 0 , c[N] , par[N];
  25.  
  26. struct gv{
  27.     int val , id;
  28. };
  29.  
  30. gv b[N];
  31.  
  32. bool cmp(gv x , gv y){
  33.     return x.val > y.val;
  34. }
  35.  
  36. void inp(){
  37.     cin >> n >> m;
  38.     for (int i = 1 ; i <= n + 1 ; ++i){
  39.         par[i] = i;
  40.     }
  41.     for (int i = 1 ; i < n ; ++i){
  42.         int u , v;
  43.         cin >> u >> v;
  44.         a[u].push_back(v);
  45.         adj[v].push_back(u);
  46.         ++c[v];
  47.     }
  48. }
  49.  
  50. int find_par(int u){
  51.     if (u == par[u]) return u;
  52.     return par[u] = find_par(par[u]);
  53. }
  54.  
  55. void bfs(){
  56.     queue<int> q;
  57.     for (int i = 1 ; i <= n ; ++i) if (c[i] == 0){
  58.         q.push(i);
  59.         ++p;
  60.         topo[p] = i;
  61.     }
  62.  
  63.     while (q.size()){
  64.         int u = q.front();
  65.         q.pop();
  66.  
  67.         for (int v : a[u]){
  68.             --c[v];
  69.             if (c[v] == 0){
  70.                 q.push(v);
  71.                 ++p;
  72.                 topo[p] = v;
  73.             }
  74.         }
  75.     }
  76. }
  77.  
  78. void solve(){
  79.     bfs();
  80.     for (int i = p ; i >= 1 ; --i){
  81.         int u = topo[i];
  82.  
  83.         int depth = 1;
  84.         for (int v : a[u]) depth = max(depth , b[v].val + 1);
  85.         b[u].val = depth;
  86.         b[u].id = u;
  87.     }
  88.     sort(b + 1 , b + n + 1 , cmp);
  89.     int res = 0;
  90.     for (int i = 1 ; i <= p ; ++i){
  91.         int u = b[i].id;
  92.         int _max = 0;
  93.         for (int v : adj[u]) _max = max(_max , col[v]);
  94.         int need = _max + 1;
  95.         int color = find_par(need);
  96.  
  97.         col[u] = color;
  98.         res = max(res , color);
  99.         cnt[color]++;
  100.  
  101.         if (cnt[color] == m)
  102.         par[color] = find_par(color + 1);
  103.     }
  104.     cout << res;
  105. }
  106.  
  107. int main(){
  108.     faster;
  109.     inp();
  110.     solve();
  111.     return 0;
  112. }
  113.  
Success #stdin #stdout 0.01s 20096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/F40f59
language:
C++14 (gcc 8.3)
created:
13 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!