Advertisement
wym1111

Untitled

Oct 9th, 2024
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.79 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 4e4 + 10;
  7. const int M = 1e9;
  8.  
  9. class Segment {
  10. private:
  11.     struct Node {
  12.         int lson, rson;
  13.         int sum;
  14.     } node[N << 5];
  15.     int idx;
  16. public:
  17. #define ls(x) node[x].lson
  18. #define rs(x) node[x].rson
  19.     void init () {
  20.         idx = 0;
  21.         node[idx] = {0, 0, 0};
  22.     }
  23.     void push_up (int p) {
  24.         node[p].sum = node[ls(p)].sum + node[rs(p)].sum;
  25.     }
  26.     int update (int p, int x, int v, int s, int t) {
  27.         if (!p) {
  28.             p = ++ idx;
  29.             node[p] = {0, 0, 0};
  30.         }
  31.         if (s == t) {
  32.             node[p].sum += v;
  33.             return p;
  34.         }
  35.         int mid = (s + t) >> 1;
  36.         if (x <= mid) ls(p) = update(ls(p), x, v, s, mid);
  37.         else rs(p) = update(rs(p), x, v, mid + 1, t);
  38.         push_up(p);
  39.         return p;
  40.     }
  41.     int query (int p, int l, int r, int s, int t) {
  42.         if (!p) return 0;
  43.         if (l <= s && t <= r) {
  44.             return node[p].sum;
  45.         }
  46.         int mid = (s + t) >> 1;
  47.         int res = 0;
  48.         if (l <= mid) res = query(ls(p), l, r, s, mid);
  49.         if (mid < r) res += query(rs(p), l, r, mid + 1, t);
  50.         return res;
  51.     }
  52. };
  53. Segment seg;
  54.  
  55. int n;
  56. int lim_l, lim_w;
  57. vector<pair<int, int>> t[N];
  58. bool vis[N];
  59.  
  60. void init () {
  61.     cin >> n >> lim_l >> lim_w;
  62.     for (int i = 1; i <= n; i ++) {
  63.         t[i].clear();
  64.         vis[i] = 0;
  65.     }
  66.     for (int i = 2; i <= n; i ++) {
  67.         int p, w;
  68.         cin >> p >> w;
  69.         t[p].push_back({i, w});
  70.         t[i].push_back({p, w});
  71.     }
  72. }
  73.  
  74. int sz[N], mx[N], rt, tot;
  75.  
  76. void findroot (int x, int fa) {
  77.     sz[x] = 1;
  78.     mx[x] = 0;
  79.     for (auto [y, w]: t[x]) {
  80.         if (y == fa || vis[y]) continue;
  81.         findroot(y, x);
  82.         sz[x] += sz[y];
  83.         mx[x] = max(mx[x], sz[y]);
  84.     }
  85.     mx[x] = max(mx[x], tot - mx[x] - 1);
  86.     if (mx[x] < mx[rt]) rt = x;
  87. }
  88.  
  89. ll ans = 0, ans2 = 0;
  90. vector<pair<int, int>> vec;
  91.  
  92. void add (int x, int fa, int len, int weight) {
  93.     vec.push_back({len, weight});
  94.     for (auto [y, w]: t[x]) {
  95.         if (y == fa || vis[y]) continue;
  96.         add(y, x, len + 1, weight + w);
  97.     }
  98. }
  99.  
  100. void cal (int x, int fa, int opt) {
  101.     seg.init();
  102.     int seg_rt = 0;
  103.     vec.clear();
  104.     if (opt < 0) vec.push_back({1, -opt});
  105.     for (auto [y, w]: t[x]) {
  106.         if (y == fa || vis[y]) continue;
  107.         if (opt > 0) add(y, x, 1, w);
  108.         else add(y, x, 2, w - opt);
  109.     }
  110.     sort(vec.begin(), vec.end());
  111.    
  112.     int p = vec.size() - 1;
  113.     for (auto [len, w]: vec) {
  114.         if (p < 0 || len > lim_l) break;
  115.         if (len + vec[p].first <= lim_l) {
  116.             seg_rt = seg.update(seg_rt, w, 1, 0, M);
  117.         } else if (p >= 0) {
  118.             if (vec[p].second <= lim_w) {
  119.                 int res = seg.query(seg_rt, 0, lim_w - vec[p].second, 0, M);
  120. //              cout << vec[p].first << ' ' << vec[p].second << ' ' << res << endl;
  121.                 if (opt > 0) ans += res;
  122.                 else ans -= res;
  123.             }
  124.             p --;
  125.         }
  126.     }
  127.     while (p >= 0) {
  128.         if (vec[p].second < lim_w) {
  129.             int res = seg.query(seg_rt, 0, lim_w - vec[p].second, 0, M);
  130. //          cout << vec[p].first << ' ' << vec[p].second << ' ' << res << endl;
  131.             if (opt > 0) ans += res;
  132.             else ans -= res;
  133.         }
  134.         p --;
  135.     }
  136.     if (opt > 0) {
  137.         cout << "add: " << fa << " -> " << x << endl;
  138.         for (auto [len, w]: vec) {
  139.             if (len > lim_l) break;
  140.             if (w <= lim_w) ans2 ++;
  141.         }
  142.     }
  143. }
  144.  
  145. void dfz (int x, int fa) {
  146. //  cout << "dfz: " << fa << " -> " << x << endl;
  147.     vis[x] = 1;
  148.     cal(x, fa, 1);
  149. //  cout << "add: " << ans << endl;
  150.     for (auto [y, w]: t[x]) {
  151.         if (y == fa || vis[y]) continue;
  152.         cal(y, x, -w);
  153. //      cout << "del: " << y << ' ' << ans << endl;
  154.     }
  155.    
  156.     for (auto [y, w]: t[x]) {
  157.         if (y == fa || vis[y]) continue;
  158.         tot = sz[y];
  159.         rt = 0;
  160.         findroot(y, x);
  161.         findroot(rt, 0);
  162.         dfz(rt, x);
  163.     }
  164. }
  165.  
  166. void solve () {
  167.     init();
  168.    
  169.     tot = n;
  170.     rt = 0;
  171.     mx[rt] = n;
  172.     findroot(1, 0);
  173.     findroot(rt, 0);
  174.    
  175.     dfz(rt, 0);
  176.     cout << ans / 2 + ans2 << endl;
  177.    
  178.     cout << ans << ' ' << ans2 << endl;
  179. }
  180.  
  181. signed main () {
  182.     ios::sync_with_stdio(0);
  183.     cin.tie(0);
  184.    
  185.     int _ = 1;
  186. //  cin >> _;
  187.     while (_ --) {
  188.         solve();
  189.     }
  190.    
  191.     return 0;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement