#include #include #include using namespace std; #define INF 2000000000000000000ll int n; vector > sons; vector salary; vector sizes; // Interval vector > postorder; int postord(int x, int num) { int last = num; int size = 1; for (int i = 0; i < sons[x].size(); i++) { last = postord(sons[x][i], last); size += sizes[sons[x][i]]; } sizes[x] = size; postorder[x] = make_pair(num, last); return last+1; } int is = 131072; typedef long long ll; struct Inter { ll sum; ll min; ll pending_change; ll pending_add; Inter() : sum(0), min(0), pending_change(-1), pending_add(0) {} }; Inter strom[1234567]; pair add(ll a, int my_begin, int my_end, int a_begin, int a_end, int v); pair change(ll ch, int my_begin, int my_end, int a_begin, int a_end, int v); void push_down(int my_begin, int my_end, int v) { if (strom[v].pending_change != -1) { change(strom[v].pending_change, my_begin, (my_begin+my_end)/2, my_begin, my_end, 2*v); change(strom[v].pending_change, (my_begin+my_end)/2, my_end, my_begin, my_end, 2*v+1); strom[v].pending_change = -1; } if (strom[v].pending_add != 0) { add(strom[v].pending_add, my_begin, (my_begin+my_end)/2, my_begin, my_end, 2*v); add(strom[v].pending_add, (my_begin+my_end)/2, my_end, my_begin, my_end, 2*v+1); strom[v].pending_add = 0; } } // Vrací pair add(ll a, int my_begin, int my_end, int a_begin, int a_end, int v) { if (my_begin >= a_end || my_end <= a_begin) return make_pair(strom[v].sum, strom[v].min); if (my_begin >= a_begin && my_end <= a_end) { strom[v].pending_add += a; strom[v].min += a; strom[v].sum += (my_end - my_begin) * a; return make_pair(strom[v].sum, strom[v].min); } push_down(my_begin, my_end, v); pair r1 = add(a, my_begin, (my_end+my_begin)/2, a_begin, a_end, 2*v); pair r2 = add(a, (my_end+my_begin)/2, my_end, a_begin, a_end, 2*v+1); strom[v].sum = r1.first+r2.first; strom[v].min = min(r1.second, r2.second); return make_pair(strom[v].sum, strom[v].min); } void add(ll a, int a_begin, int a_end) { add(a, 1, is, a_begin, a_end, 1); } pair change(ll ch, int my_begin, int my_end, int a_begin, int a_end, int v) { if (my_begin >= a_end || my_end <= a_begin) return make_pair(strom[v].sum, strom[v].min); if (my_begin >= a_begin && my_end <= a_end) { strom[v].pending_add = 0; strom[v].pending_change = ch; strom[v].min = ch; strom[v].sum = ch*(my_end - my_begin); return make_pair(strom[v].sum, strom[v].min); } push_down(my_begin, my_end, v); pair r1 = change(ch, my_begin, (my_end+my_begin)/2, a_begin, a_end, 2*v); pair r2 = change(ch, (my_end+my_begin)/2, my_end, a_begin, a_end, 2*v+1); strom[v].sum = r1.first+r2.first; strom[v].min = min(r1.second, r2.second); return make_pair(strom[v].sum, strom[v].min); } void change(ll ch, int a_begin, int a_end) { change(ch, 1, is, a_begin, a_end, 1); } pair get(int my_begin, int my_end, int a_begin, int a_end, int v) { if (my_begin >= a_end || my_end <= a_begin) return make_pair(0, INF); if (my_begin >= a_begin && my_end <= a_end) { return make_pair(strom[v].sum, strom[v].min); } push_down(my_begin, my_end, v); pair r1 = get(my_begin, (my_end+my_begin)/2, a_begin, a_end, 2*v); pair r2 = get((my_end+my_begin)/2, my_end, a_begin, a_end, 2*v+1); return make_pair(r1.first + r2.first, min(r1.second, r2.second)); } ll get_min(int a_begin, int a_end) { return get(1, is, a_begin, a_end, 1).second; } ll get_sum(int a_begin, int a_end) { return get(1, is, a_begin, a_end, 1).first; } int main() { scanf("%d", &n); salary.resize(n); sons.resize(n); sizes.resize(n); postorder.resize(n); for (int i = 0; i < n; i++) { int p; scanf("%d %d", &salary[i], &p); sons[i].resize(p); for (int j = 0; j < p; j++) { scanf("%d", &sons[i][j]); sons[i][j]--; } } postord(0, 1); for (int i = 0; i < n; i++) change(salary[i], postorder[i].second, postorder[i].second+1); int q; scanf("%d", &q); for (int o = 0; o < q; o++) { int a, u, x, y; scanf("%d %d", &a, &u); if (a != 3) scanf("%d %d", &x, &y); u--; if (a == 1) { if (get_sum(postorder[u].second, postorder[u].second+1) < x) { add(y, postorder[u].second, postorder[u].second+1); } } else if (a == 2) { if (get_sum(postorder[u].first, postorder[u].second+1) < x * sizes[u]) { add(y, postorder[u].first, postorder[u].second+1); } } else { ll mi = get_min(postorder[u].first, postorder[u].second+1); change(mi, postorder[u].first, postorder[u].second+1); } } for (int i = 0; i < n; i++) printf("%lld\n", get_min(postorder[i].second, postorder[i].second+1)); return 0; }