fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. using ll = long long;
  7. const int N = 3e5 + 5;
  8. int n, l, r, sz[N], h[N];
  9. bool del[N];
  10. vector<int> G[N], ADD;
  11. ll ans = 0, bit[N];
  12. int vers = 0, vis[N];
  13.  
  14. inline void dfs(int u, int pre) {
  15.     sz[u] = 1;
  16.     for (int v: G[u]) if (v != pre && !del[v]) {
  17.         dfs(v, u);
  18.         sz[u] += sz[v];
  19.     }
  20. }
  21.  
  22. inline int centroid(int u, int pre, int n) {
  23.     for (int v: G[u]) if (v != pre && !del[v]) {
  24.         if (sz[v] * 2 > n) return centroid(v, u, n);
  25.     }
  26.     return u;
  27. }
  28. inline void update(int id, ll t) {
  29.     for (; id <= n; id += id &- id) {
  30.         if (vis[id] != vers) {
  31.             vis[id] = vers;
  32.             bit[id] = 0;
  33.         }
  34.         bit[id] += t;
  35.     }
  36. }
  37.  
  38. inline ll get(int id) {
  39.     if (id == 0) return 1;
  40.     ll ans = 1;
  41.     for (; id; id -= id &- id) {
  42.         if (vis[id] != vers) {
  43.             vis[id] = vers;
  44.             bit[id] = 0;
  45.         }
  46.         ans += bit[id];
  47.     }
  48.     return ans;
  49. }
  50.  
  51. inline void calc(int u, int pre) {
  52.     h[u] = h[pre] + 1;
  53.     if (h[u] > r) return;
  54.  
  55.     ans += get(r - h[u]);
  56.     if (l >= h[u]) ans -= get(l - h[u]);
  57.  
  58.     ADD.push_back(h[u]);
  59.  
  60.     for (int v: G[u]) if (v != pre && !del[v]) calc(v, u);
  61. }
  62.  
  63. inline void build(int u) {
  64.     dfs(u, 0);
  65.     int n = sz[u];
  66.     u = centroid(u, u, n);
  67.  
  68.     vers++;
  69.     h[u] = 0;
  70.     for (int v: G[u]) if (!del[v])  {
  71.         calc(v, u);
  72.         for (int i: ADD) update(i, 1);
  73.         ADD.clear();
  74.     }
  75.  
  76.     del[u] = true;
  77.     for (int v: G[u]) if (!del[v]) {
  78.         build(v);
  79.     }
  80. }
  81.  
  82. signed main() {
  83.     cin.tie(NULL)->sync_with_stdio(false);
  84.     if(ifstream("Input.inp")) {
  85.         freopen("Input.inp", "r", stdin);
  86.         freopen("Output.out", "w", stdout);
  87.     }
  88.     cin >> n >> l >> r;
  89.     l--;
  90.     for (int i = 1; i < n; i++) {
  91.         int u, v; cin >> u >> v;
  92.         G[u].push_back(v);
  93.         G[v].push_back(u);
  94.     }
  95.     build(1);
  96.     cout << ans;
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 15840KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/A2b9Uv
language:
C++14 (gcc 8.3)
created:
2 days 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!