fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. #define MP make_pair
  7. #define PB push_back
  8. #define ll long long
  9. #define pii pair<int, int>
  10. #define SZ(a) int(a.size())
  11. #define ALL(a) a.begin(), a.end()
  12. #define MS(a, v) memset(a, v, sizeof a)
  13. #define REP(i, n) for(int i = 0; i < n; ++ i)
  14. #define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
  15. #define FOD(i, a, b) for(int i = (a); i >= (b); -- i)
  16. #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout)
  17.  
  18. template<class X, class Y>
  19.         bool maximize(X & x, const Y & y){
  20.                 if(x < y){
  21.                         x = y;
  22.                         return true;
  23.                 }
  24.                 else return false;
  25.         }
  26.  
  27. template<class X, class Y>
  28.         bool minimize(X & x, const Y & y){
  29.                 if(x > y){
  30.                         x = y;
  31.                         return true;
  32.                 }
  33.                 else return false;
  34.         }
  35.  
  36. const int MAXN = 200005;
  37. const int MOD = 1e9 + 7;
  38. const ll INF = 1e18;
  39.  
  40. int n, m;
  41. ll v[MAXN];
  42. vector <int> g[MAXN];
  43.  
  44. int in[MAXN], out[MAXN], Time;
  45.  
  46. void dfs(int u){
  47.         in[u] = ++ Time;
  48.         for(int v : g[u]){
  49.                 dfs(v);
  50.         }
  51.         out[u] = Time;
  52. }
  53.  
  54. ll st[MAXN];
  55. ll lz[MAXN << 2];
  56.  
  57. void up(int id, int l, int r, int u, int v, int val){
  58.         if(u > r || v < l) return;
  59.         if(u <= l && r <= v){
  60.                 lz[id] += val;
  61.                 if(l == r) st[l] += val;
  62.                 return;
  63.         }
  64.         int mid = (l + r) >> 1;
  65.         FOR(i, id * 2, id * 2 + 1)
  66.                 lz[i] += lz[id];
  67.         if(l == mid) st[l] += lz[id];
  68.         if(mid + 1 == r) st[r] += lz[id];
  69.         lz[id] = 0;
  70.         up(id << 1, l, mid, u, v, val);
  71.         up(id << 1 ^ 1, mid + 1, r, u, v, val);
  72. }
  73.  
  74. ll get(int id, int l, int r, int i){
  75.         if(i > r || i < l) return 0;
  76.         if(l == r) return st[l];
  77.         int mid = (l + r) >> 1;
  78.         FOR(i, id * 2, id * 2 + 1)
  79.                 lz[i] += lz[id];
  80.         if(l == mid) st[l] += lz[id];
  81.         if(mid + 1 == r) st[r] += lz[id];
  82.         lz[id] = 0;
  83.         return get(id << 1, l, mid, i) + get(id << 1 ^ 1, mid + 1, r, i);
  84. }
  85.  
  86. void solve(void){
  87.         cin >> n >> m;
  88.         cin >> v[1];
  89.         FOR(i, 2, n){
  90.                 cin >> v[i];
  91.                 int x; cin >> x;
  92.                 g[x].PB(i);
  93.         }
  94.         dfs(1);
  95. //        FOR(i, 1, n) up(1, 1, n, in[i], in[i], v[i]);
  96.  
  97.         char t;
  98.         int u, x;
  99.         FOR(i, 1, m){
  100.                 cin >> t >> u;
  101.                 if(t == 'p'){
  102.                         cin >> x;
  103.                         up(1, 1, n, in[u] + 1, out[u], x);
  104.                 }
  105.                 else{
  106.                         cout << v[u] + get(1, 1, n, in[u]) << "\n";
  107.                 }
  108.         }
  109. }
  110.  
  111. int main(void){
  112.  
  113.         ios_base :: sync_with_stdio(0);
  114.         cin.tie(0); cout.tie(0);
  115.  
  116.         #define TaZinh "salary"
  117.  
  118.         if(fopen(TaZinh".inp", "r"))
  119.                 TSun(TaZinh);
  120.  
  121.         int Sun = 1;
  122. //        cin >> Sun;
  123.         REP(love, Sun) solve();
  124.  
  125.         return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 10160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TXGaku
language:
C++ (gcc 8.3)
created:
80 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!