fork download
copy 
  1. // Shaazzz
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int N = 1e6 + 10;
  5. int n, k;
  6. pair < int , int > dp[N];
  7. vector < int > Adj[N];
  8. void DFS(int v, int p)
  9. {
  10.     int Mx1 = 0, Mx2 = 0;
  11.     for (int &u : Adj[v])
  12.         if (u != p)
  13.         {
  14.             DFS(u, v);
  15.             dp[v].first += dp[u].first;
  16.             if (dp[u].second >= Mx2)
  17.                 Mx2 = dp[u].second;
  18.             if (Mx2 >= Mx1)
  19.                 swap(Mx1, Mx2);
  20.         }
  21.     if (Mx1 + Mx2 + 1 >= k + 1)
  22.         dp[v].first ++;
  23.     else
  24.         dp[v].second = Mx1 + 1;
  25. }
  26. int main()
  27. {
  28.     scanf("%d%d", &n, &k);
  29.     for (int i = 1; i < n; i++)
  30.     {
  31.         int v, u;
  32.         scanf("%d%d", &u, &v);
  33.         Adj[v].push_back(u);
  34.         Adj[u].push_back(v);
  35.     }
  36.     DFS(1, 0);
  37.     return !printf("%d", dp[1].first);
  38. }
Success #stdin #stdout 0s 46488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/UMv9d6
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!