fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define max max<int>
  4. using namespace std;
  5.  
  6. constexpr int N = 1e5 + 5;
  7.  
  8. int n, k;
  9. vector<int> children[N];
  10. bool hasparent[N] = {false};
  11. int tree[N] = {0};
  12.  
  13. int get(int i) {
  14.     int s = 0;
  15.     for (; i; i -= i & -i) {
  16.         s += tree[i];
  17.     }
  18.     return s;
  19. }
  20.  
  21. void update(int i, int x) {
  22.     for (; i <= n; i += i & -i) {
  23.         tree[i] += x;
  24.     }
  25. }
  26.  
  27. int timer;
  28. int res;
  29.  
  30. void dfs(int u)
  31. {
  32.     ++timer;
  33.     update(u, 1);
  34.  
  35.     int lo = max(u - k - 1, 0);
  36.     int hi = min(u + k, n);
  37.     res -= get(hi) - get(lo);
  38.  
  39.     for (int v : children[u]) {
  40.         dfs(v);
  41.     }
  42.  
  43.     res += get(hi) - get(lo);
  44. }
  45.  
  46. signed main()
  47. {
  48.     ios::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.     cout.tie(NULL);
  51.  
  52.     // freopen("input.txt", "r", stdin);
  53.  
  54.     cin >> n >> k;
  55.  
  56.     for (int e = 1; e < n; e++) {
  57.         int u, v;
  58.         cin >> u >> v;
  59.  
  60.         children[u].push_back(v);
  61.         hasparent[v] = true;
  62.     }
  63.  
  64.     timer = 0;
  65.     res = 0;
  66.     for (int r = 1; r <= n; r++) {
  67.         if (hasparent[r]) continue;
  68.         dfs(r);
  69.         break;
  70.     }
  71.  
  72.     cout << res;
  73.  
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 5936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7Bh4OQ
language:
C++14 (gcc 8.3)
created:
1 day 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!