include iostream include vector include string using namespace std int

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int sal[100000];
int index = 0;
vector<int> dep;
vector<int> salary;
int order[100000] = {0};
long long tree[400000] = {0};
long long mod[400000] = {0};
vector<vector<int> > g;
void build_tree(int l, int r, int v) {
if (l == r - 1) {
tree[v] = salary[l];
return;
}
int m = (l + r) / 2;
build_tree(l, m, 2 * v + 1);
build_tree(m, r, 2 * v + 2);
tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
}
void apply(int l, int r, int v, long long d) {
tree[v] += (r - l) * d;
mod[v] += d;
}
void push(int l, int r, int v) {
if (mod[v]) {
int m = (l + r) / 2;
apply(l, m, 2 * v + 1, mod[v]);
apply(m, r, 2 * v + 2, mod[v]);
mod[v] = 0;
}
}
void add(int ql, int qr, int l, int r, long long d, int v) {
if (ql == l && qr == r) {
apply(l, r, v, d);
return;
}
int m = (l + r) / 2;
push(l, r, v);
if (qr <= m)
add(ql, qr, l, m, d, 2 * v + 1);
else if (ql >= m)
add(ql, qr, m, r, d, 2 * v + 2);
else {
add(ql, m, l, m, d, 2 * v + 1);
add(m, qr, m, r, d, 2 * v + 2);
}
tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
}
long long getsum(int ql, int qr, int l, int r, int v) {
if (ql == l && qr == r) {
return tree[v];
}
int m = (l + r) / 2, t;
push(l, r, v);
if (qr <= m)
t = getsum(ql, qr, l, m, 2 * v + 1);
else if(ql >= m)
t = getsum(ql, qr, m, r, 2 * v + 2);
else
t = getsum(ql, m, l, m, 2 * v + 1) + getsum(m, qr, m, r, 2 * v + 2);
return t;
}
int dfs(int v) {
dep[v] = 1;
salary.push_back(sal[v]);
order[v] = index++;
for (int i = 0; i < g[v].size(); ++i) {
dep[v] += dfs(g[v][i]);
}
return dep[v];
}
int main(){
int n, q, a, b, c;
cin >> n >> q >> sal[0];
string s;
g.resize(n);
dep.resize(n, 0);
vector<int> ans(n);
for (int i = 1; i < n; ++i) {
cin >> a >> sal[i];
g[a].push_back(i);
}
dfs(0);
build_tree(0, n, 0);
for (int i = 0; i < q; ++i) {
cin >> s >> a >> b >> c;
int ind = order[a];
if (s == "department") {
int dep_size = dep[a];
if (getsum(ind, ind + dep_size, 0, n, 0) < 1ll * b * dep_size)
add(ind, ind + dep_size, 0, n, c, 0);
}
else if (getsum(ind, ind + 1, 0, n, 0) < b) {
add(ind, ind + 1, 0, n, c, 0);
}
}
for (int i = 0; i < n; ++i)
cout << getsum(order[i], order[i] + 1, 0, n, 0) << endl;
return 0;
}