fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define all(x) x.begin(), x.end()
  6. const int N = 1e5 + 5;
  7. const int INF = 1e18;
  8.  
  9. struct SegTree {
  10.     struct Node{
  11.         int val, zero, mn;
  12.     };
  13.     int n;
  14.     vector<Node> tree;
  15.     vector<int> lazy;
  16.     #define LEFT node * 2 + 1
  17.     #define RIGHT node * 2 + 2
  18.  
  19.     SegTree(vector<int> &arr) {
  20.         this->n = arr.size();
  21.         tree.resize(4 * n);
  22.         lazy.assign(4 * n, 0); // 1
  23.         build(0, 0, n - 1, arr);
  24.     }
  25.  
  26.     Node merge(Node a, Node b) {
  27.         Node r;
  28.         r.val = a.val + b.val;
  29.         r.zero = a.zero + b.zero;
  30.         r.mn = min(a.mn, b.mn);
  31.         return r;
  32.     }
  33.  
  34.     void build(int node, int start, int end, vector<int>& arr) {
  35.         if (start == end) {
  36.             tree[node] = {arr[start], arr[start] == 0, arr[start]};
  37.             return;
  38.         }
  39.         int mid = (start + end) / 2;
  40.         build(LEFT, start, mid, arr);
  41.         build(RIGHT, mid + 1, end, arr);
  42.         tree[node] = merge(tree[LEFT], tree[RIGHT]);
  43.     }
  44.  
  45.     void apply(int node, int start, int end, int val) {
  46.         tree[node].mn -= val;
  47.         tree[node].val -= (start - end + 1) * val; // 3
  48.         lazy[node] += val;
  49.     }
  50.  
  51.     void push(int node, int start, int end) {
  52.         if (!lazy[node]) return;
  53.         if (start == end) {
  54.             lazy[node] = 0;
  55.             return;
  56.         }
  57.         int mid = (start + end) / 2;
  58.         apply(LEFT, start, mid, lazy[node]);
  59.         apply(RIGHT, mid + 1, end, lazy[node]);
  60.         lazy[node] = 0;
  61.     }
  62.  
  63.     void update(int node, int start, int end, int L, int R, int val) {
  64.         if (R < start || end < L || !tree[node].val) return; // 4
  65.         if (L <= start && end <= R && tree[node].mn > val){ // 2
  66.             apply(node, start, end, val);
  67.             return;
  68.         }
  69.         if(start == end){
  70.             tree[node].val = max(0ll, tree[node].val - val);
  71.             tree[node].zero = tree[node].val == 0;
  72.             tree[node].mn = tree[node].val;
  73.             return;
  74.         }
  75.         push(node, start, end);
  76.         int mid = (start + end) / 2;
  77.         update(LEFT, start, mid, L, R, val);
  78.         update(RIGHT, mid + 1, end, L, R, val);
  79.         tree[node] = merge(tree[LEFT], tree[RIGHT]);
  80.     }
  81.  
  82.     Node query(int node, int start, int end, int L, int R) {
  83.         if (R < start || end < L) return {0, 0, INF};
  84.         if (L <= start && end <= R) return tree[node];
  85.         push(node, start, end);
  86.         int mid = (start + end) / 2;
  87.         return merge(query(LEFT, start, mid, L, R), query(RIGHT, mid + 1, end, L, R));
  88.     }
  89.  
  90.     // 0-indexed
  91.     void update(int L, int R, int val){
  92.         if(L > R) return;
  93.         update(0, 0, n - 1, L, R, val);
  94.     }
  95.     Node query(int L, int R) {
  96.         if(L > R) return {0, 0, INF};
  97.         return query(0, 0, n - 1, L, R);
  98.     }
  99. };
  100.  
  101. vector<int> flat;
  102. int a[N], in[N], out[N];
  103. vector<int> g[N];
  104. int timer = 0;
  105.  
  106. void dfs(int node, int par){
  107.     in[node] = timer++;
  108.     flat.push_back(a[node]);
  109.     for(auto next : g[node]){
  110.         if(next == par) continue;
  111.         dfs(next, node);
  112.     }
  113.     out[node] = timer - 1;
  114. }
  115.  
  116.  
  117. void solve() {
  118.     int n;
  119.     cin >> n;
  120.     for(int i = 1; i <= n; i++){
  121.         int h, p;
  122.         cin >> h >> p;
  123.         a[i] = h;
  124.         g[i].push_back(p);
  125.         g[p].push_back(i);
  126.     }
  127.     // for(int i = 0; i <= n; i++) cout << a[i] << ' ';
  128.     // cout << '\n';
  129.     dfs(0, -1);
  130.  
  131.     int q;
  132.     cin >> q;
  133.     SegTree st(flat);
  134.     while(q--){
  135.         int t, v, x;
  136.         cin >> t >> v;
  137.         if(t == 1){
  138.             cin >> x;
  139.             st.update(in[v] + 1, out[v], x);
  140.         }else{
  141.             cout << (out[v] - in[v]) - st.query(in[v] + 1, out[v]).zero << '\n';
  142.         }
  143.     }
  144. }
  145.  
  146. signed main() {
  147.   ios_base::sync_with_stdio(false);
  148.   cin.tie(nullptr);
  149.   int tc = 1;
  150.   // cin >> tc;
  151.   for (int i = 0; i < tc; i += 1) {
  152.     solve();
  153.   }
  154.   return 0;
  155. }
  156.  
Success #stdin #stdout 0.01s 7476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QzldAj
language:
C++ (gcc 8.3)
created:
10 hours 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!