fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 2e5 + 5;
  4. const int magic = 1000;
  5.  
  6. int n, lo[maxn], a[maxn], d[maxn], freq[maxn / magic + 1][2 * maxn];
  7. vector<int> hi[maxn];
  8.  
  9. void update(int idx, int add) {
  10.     if (idx % magic > 0) {
  11.         int bucket = idx / magic;
  12.         int end = min(idx - idx % magic + magic - 1, n);
  13.         for (int i = idx; i <= end; i++) {
  14.             --freq[bucket][a[i] + maxn];
  15.             a[i] += add;
  16.             ++freq[bucket][a[i] + maxn];
  17.         }
  18.         idx = end + 1;
  19.     }
  20.     while (idx <= n) {
  21.         d[idx / magic] += add;
  22.         idx += magic;
  23.     }
  24. }
  25.  
  26. int query() {
  27.     int ret = 0;
  28.     for (int i = 0; i * magic <= n; i++) {
  29.         ret += freq[i][-d[i] + maxn];
  30.     }
  31.     return ret;
  32. }
  33.  
  34. int main() {
  35.     scanf("%d", &n);
  36.     for (int i = 0; i < n - 1; i++) {
  37.         int u, v;
  38.         scanf("%d%d", &u, &v);
  39.         ++lo[max(u, v)];
  40.         hi[min(u, v)].push_back(max(u, v));
  41.     }
  42.     a[0] = freq[0][1 + maxn] = 1;
  43.     for (int i = 1; i <= n; i++) {
  44.         a[i] = a[i - 1] + lo[i] - 1;
  45.         ++freq[i / magic][a[i] + maxn];
  46.     }
  47.     long long res = 0;
  48.     for (int i = 1; i <= n; i++) {
  49.         res += query();
  50.         for (int h : hi[i]) {
  51.             update(h, -1);
  52.         }
  53.         update(0, 1);
  54.     }
  55.     cout << res << '\n';
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0s 322240KB
comments (?)
stdin 
3
1 3
3 2
stdout 
5
https://ideone.com/hVosff
language:
C++14 (gcc 8.3)
created:
8 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!