fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty