fork download
copy 
  1. #include <bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp>
  3. //#include <ext/pb_ds/tree_policy.hpp>
  4. //#include <ext/pb_ds/detail/standard_policies.hpp>
  5.  
  6. //#pragma GCC optimize("O3")
  7.  
  8. using namespace std;
  9. //using namespace __gnu_pbds;
  10.  
  11. template<typename T>
  12. inline void read(T& x) {
  13.   x = 0;
  14.   char c = getchar();
  15.   bool _ = false;
  16.   while (c < '0' || c > '9') _ |= c == '-', c = getchar();
  17.   while (c >= '0' && c <= '9') {
  18.     x *= 10;
  19.     x += c - '0';
  20.     c = getchar();
  21.   }
  22.   if (_) x = -x;
  23. }
  24.  
  25. #define F first
  26. #define S second
  27. #define pb push_back
  28. #define mt make_tuple
  29. //#define mp make_pair
  30.  
  31. //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  32.  
  33. typedef long long ll;
  34. //typedef long double ld;
  35.  
  36. const int rx[4] = {-1, 0, 1, 0};
  37. const int ry[4] = {0, -1, 0, 1};
  38. /// U L D R
  39.  
  40. typedef pair<int,int> T;
  41.  
  42. struct segtree {
  43.   int n;
  44.   vector<T> t;
  45.   vector<int> d;
  46.   int h;
  47.   void apply(int p, int value) {
  48.     t[p].F += value;
  49.     if (p < n) d[p] += value;
  50.   }
  51.   T unite(T a, T b) {
  52.     if (a.F == b.F) {
  53.       return make_pair(a.F, a.S + b.S);
  54.     } else {
  55.       return max(a, b);
  56.     }
  57.   }
  58.   void recalc(int p) {
  59.     while (p > 1) {
  60.       p >>= 1;
  61.       t[p] = unite(t[p << 1], t[p << 1|1]);
  62.       t[p].F += d[p];
  63.     }
  64.   }
  65.   void push(int p) {
  66.     for (int s = h; s > 0; --s) {
  67.       int i = p >> s;
  68.       if (d[i] != 0) {
  69.         apply(i << 1, d[i]);
  70.         apply(i << 1|1, d[i]);
  71.         d[i] = 0;
  72.       }
  73.     }
  74.   }
  75.   void inc(int l, int r, int value) {
  76.     l += n, r += n;
  77.     int l0 = l, r0 = r;
  78.     for (; l < r; l >>= 1, r >>= 1) {
  79.       if (l & 1) apply(l++, value);
  80.       if (r & 1) apply(--r, value);
  81.     }
  82.     recalc(l0);
  83.     recalc(r0 - 1);
  84.   }
  85.   T query(int l, int r) {
  86.     l += n, r += n;
  87.     push(l);
  88.     push(r - 1);
  89.     T res = make_pair(-2e9, 0);
  90.     for (; l < r; l >>= 1, r >>= 1) {
  91.       if (l & 1) res = unite(res, t[l++]);
  92.       if (r & 1) res = unite(t[--r], res);
  93.     }
  94.     return res;
  95.   }
  96.   segtree(int n): n(n), t(n << 1, make_pair(0, 1)), h(32 - __builtin_clz(n)), d(n, 0) {
  97.     for (int i = n; i < n + n; i++) {
  98.       t[i].F = -(i - n);
  99.     }
  100.     for (int i = n; i < n + n; i++) {
  101.       recalc(i);
  102.     }
  103.   }
  104. };
  105.  
  106. const int N = 1000100;
  107.  
  108. vector<int> g[N];
  109. int n, q;
  110. ll ans = 0;
  111. int sum[N];
  112.  
  113. void calc() {
  114.   segtree D(n);
  115.   for (int i = n - 1; i >= 0; i--) {
  116.     for (int x : g[i]) {
  117.       D.inc(x, D.n, 1);
  118.     }
  119.     T cur = D.query(i, D.n);
  120.     if (cur.F == -i){
  121.       ans += cur.S;
  122.     }
  123.   }
  124. }
  125.  
  126. void solve() {
  127.   read(n);
  128.   for (int i = 0; i < n; i++) if (g[i].size()) g[i].clear();
  129.   for (int i = 0; i < n - 1; i++) {
  130.     int x, y;
  131.     read(x);
  132.     read(y);
  133.     if (x > y) swap(x, y);
  134.     g[x - 1].pb(y - 1);
  135.   }
  136.   for (int i = 0; i < n; i++) sort(g[i].begin(), g[i].end());
  137.   ans = 0;
  138.   calc();
  139.   cout << ans << '\n';
  140. }
  141.  
  142. #define FILE "solid"
  143. int main() {
  144.   ios_base::sync_with_stdio(0);
  145. #ifdef LOCAL
  146.   freopen("input.txt", "r", stdin);
  147. //  freopen("output.txt", "w", stdout);
  148. #else
  149. //  freopen(FILE".in", "r", stdin);
  150. //  freopen(FILE".out", "w", stdout);
  151. #endif // LOCAL
  152.   read(q);
  153.   while (q--) {
  154.     solve();
  155.   }
  156. #ifdef LOCAL
  157.   cerr << "TIME = " << fixed << 1.0 * clock() / CLOCKS_PER_SEC << endl;
  158. #endif // LOCAL
  159.   return 0;
  160. }
Time limit exceeded #stdin #stdout 5s 43416KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QysXX1
language:
C++14 (gcc 8.3)
created:
7 years 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!