#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
class bit{
public:
int n;
ll* d;
void init(int nw){
n = nw;
d = new ll[n];
for (int i = 0; i < n; i++) d[i] = 0;
}
void add(int a, ll x){
for (int i = a + 1; i <= n; i += (i & -i)) d[i - 1] += x;
}
ll sum(int a){
ll all = 0;
for (int i = a + 1; i > 0; i -= (i & -i)) all += d[i - 1];
return all;
}
};
class rmq{
public:
int n;
ll* d;
void init(int nw){
for (n = 1; n <= nw; n *= 2){}
d = new ll[n * 2];
for (int i = 0; i < n * 2; i++) d[i] = 0;
}
void setw(int a, ll x, int nb, int ne, int p){
if (a < nb || ne <= a) return;
if (ne - nb == 1){
d[p] = x;
return;
}
setw(a, x, nb, (nb + ne) / 2, p * 2 + 1);
setw(a, x, (nb + ne) / 2, ne, p * 2 + 2);
d[p] = max(d[p * 2 + 1], d[p * 2 + 2]);
}
void set(int a, ll x){
setw(a, x, 0, n, 0);
}
ll getw(int a, int nb, int ne, int p){
if (a < nb || ne <= a) return d[p];
if (ne - nb == 1) return -1;
return max(getw(a, nb, (nb + ne) / 2, p * 2 + 1), getw(a, (nb + ne) / 2, ne, p * 2 + 2));
}
ll get(int a){
return getw(a, 0, n, 0);
}
ll all(){
return d[0];
}
};
class seg{
public:
class node{
public:
ll m;
ll a;
};
node nadd(node a, ll x){
a.a += x;
a.m += x;
return a;
}
node unit(node a, node b){
node w;
w.a = 0;
w.m = max(a.m, b.m);
return w;
}
int n;
node* d;
void init(int nw){
for (n = 1; n <= nw; n *= 2){}
d = new node[n * 2];
for (int i = 0; i < n * 2; i++){
d[i].a = 0;
d[i].m = 0;
}
}
void addw(int a, ll x, int nb, int ne, int p){
if (ne <= a) return;
if (a <= nb){
d[p] = nadd(d[p], x);
return;
}
d[p * 2 + 1] = nadd(d[p * 2 + 1], d[p].a);
d[p * 2 + 2] = nadd(d[p * 2 + 2], d[p].a);
addw(a, x, nb, (nb + ne) / 2, p * 2 + 1);
addw(a, x, (nb + ne) / 2, ne, p * 2 + 2);
d[p] = unit(d[p * 2 + 1], d[p * 2 + 2]);
}
void add(int a, ll x){
addw(a, x, 0, n, 0);
}
ll getw(int a, int nb, int ne, int p){
if (a < nb || ne <= a) return d[p].m;
if (ne - nb == 1) return -1;
d[p * 2 + 1] = nadd(d[p * 2 + 1], d[p].a);
d[p * 2 + 2] = nadd(d[p * 2 + 2], d[p].a);
d[p].a = 0;
return max(getw(a, nb, (nb + ne) / 2, p * 2 + 1), getw(a, (nb + ne) / 2, ne, p * 2 + 2));
}
ll get(int a){
return getw(a, 0, n, 0);
}
};
class seg2{
public:
bit b;
seg s;
void init(int n){
b.init(n);
s.init(n);
}
void add1(int a, ll x){
s.add(a, x);
s.add(a + 1, -x);
}
void add2(int a, ll x){
b.add(a, x);
s.add(a, x);
}
ll get(int a){
ll w1 = s.get(a);
ll w2 = b.sum(a);
return w1 - w2;
}
};
class point{
public:
int o, ob1, ob2;
int de;
int n;
ll* m1;
ll* m2;
rmq* r;
seg2 s1, s2;
void init(int nw){
n = nw;
m1 = new ll[n];
for (int i = 0; i < n; i++) m1[i] = 0;
m2 = new ll[n];
for (int i = 0; i < n; i++) m2[i] = 0;
r = new rmq[n];
s1.init(n);
s2.init(n);
}
void set1(int b1, int b2, ll x){
r[b1].set(b2, x);
ll w = r[b1].all();
s1.add1(b1, w - m1[b1]);
s2.add1(n - 1 - b1, w - m1[b1]);
m1[b1] = w;
}
void set2(int b, ll x){
s1.add2(b, x - m2[b]);
s2.add2(n - b, x - m2[b]);
m2[b] = x;
}
ll all(){
return s1.get(0);
}
ll get(int b1, int b2){
ll w1 = s1.get(b1);
ll w2 = s2.get(n - 1 - b1);
ll w3 = r[b1].get(b2);
return max(max(w1, w2), w3);
}
ll tot(int a){
return s1.b.sum(a);
}
};
class rnode{
public:
int o;
vector<int> k;
int s, sb;
int km, kmb;
};
rnode nn[555555];
point hlp[555555];
int hlpn;
int dfs1(int n){
int l = nn[n].k.size();
nn[n].km = 0;
int all = 0;
for (int i = 0; i < n; i++){
int w = dfs1(nn[n].k[i]);
if (nn[n].km < w){
nn[n].km = w;
nn[n].kmb = i;
}
all += w;
}
return all + 1;
}
void dfs2(int n, int s, int sb){
nn[n].s = s;
nn[n].sb = sb;
int l = nn[n].k.size();
if (l == 0){
hlp[s].init(sb + 1);
hlp[s].r[sb].init(1);
}
else{
int w = 0;
for (int i = 0; i < l; i++){
if (i == nn[n].kmb) dfs2(nn[n].k[i], s, sb + 1);
else{
hlp[hlpn].o = s;
hlp[hlpn].ob1 = sb;
hlp[hlpn].ob2 = w++;
dfs2(nn[n].k[i], hlpn++, 1);
}
}
hlp[s].r[sb].init(l);
}
}
void hl(){
dfs1(0);
hlpn = 1;
hlp[0].o = -1;
dfs2(0, 0, 0);
}
class query{
public:
int s;
int a;
ll c;
};
query qu[555555];
void qu12(int a, ll x){
int now = nn[a].s;
hlp[now].set2(nn[a].sb, x);
int b1 = hlp[now].ob1;
int b2 = hlp[now].ob2;
ll all = hlp[now].all();
now = hlp[now].o;
while (now >= 0){
hlp[now].set1(b1, b2, all);
b1 = hlp[now].ob1;
b2 = hlp[now].ob2;
all = hlp[now].all();
now = hlp[now].o;
}
}
ll qu3(int a){
int now = nn[a].s;
ll ma = hlp[now].get(nn[a].sb, -1);
ll all = hlp[now].tot(nn[a].sb);
int b1 = hlp[now].ob1;
int b2 = hlp[now].ob2;
now = hlp[now].o;
while (now >= 0){
ma = max(ma, all + hlp[now].get(b1, b2));
all += hlp[now].tot(b1);
b1 = hlp[now].ob1;
b2 = hlp[now].ob2;
now = hlp[now].o;
}
return ma;
}
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d%d%lld", &qu[i].s, &qu[i].a, &qu[i].c);
int allk = 1;
for (int i = 0; i < n; i++){
if (qu[i].s == 1){
nn[allk].o = qu[i].a;
nn[qu[i].a].k.push_back(allk++);
}
}
hl();
long amw = 1;
for (int i = 0; i < n; i++){
switch (qu[i].s){
case 1:
qu12(amw++, qu[i].c);
break;
case 2:
qu12(qu[i].a, qu[i].c);
break;
case 3:
printf("%lld\n", qu3(qu[i].a));
break;
}
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKCmNsYXNzIGJpdHsKcHVibGljOgoJaW50IG47CglsbCogZDsKCgl2b2lkIGluaXQoaW50IG53KXsKCQluID0gbnc7CgkJZCA9IG5ldyBsbFtuXTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgZFtpXSA9IDA7Cgl9CgoJdm9pZCBhZGQoaW50IGEsIGxsIHgpewoJCWZvciAoaW50IGkgPSBhICsgMTsgaSA8PSBuOyBpICs9IChpICYgLWkpKSBkW2kgLSAxXSArPSB4OwoJfQoKCWxsIHN1bShpbnQgYSl7CgkJbGwgYWxsID0gMDsKCQlmb3IgKGludCBpID0gYSArIDE7IGkgPiAwOyBpIC09IChpICYgLWkpKSBhbGwgKz0gZFtpIC0gMV07CgkJcmV0dXJuIGFsbDsKCX0KfTsKCmNsYXNzIHJtcXsKcHVibGljOgoJaW50IG47CglsbCogZDsKCgl2b2lkIGluaXQoaW50IG53KXsKCQlmb3IgKG4gPSAxOyBuIDw9IG53OyBuICo9IDIpe30KCQlkID0gbmV3IGxsW24gKiAyXTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG4gKiAyOyBpKyspIGRbaV0gPSAwOwoJfQoKCXZvaWQgc2V0dyhpbnQgYSwgbGwgeCwgaW50IG5iLCBpbnQgbmUsIGludCBwKXsKCQlpZiAoYSA8IG5iIHx8IG5lIDw9IGEpIHJldHVybjsKCQlpZiAobmUgLSBuYiA9PSAxKXsKCQkJZFtwXSA9IHg7CgkJCXJldHVybjsKCQl9CgkJc2V0dyhhLCB4LCBuYiwgKG5iICsgbmUpIC8gMiwgcCAqIDIgKyAxKTsKCQlzZXR3KGEsIHgsIChuYiArIG5lKSAvIDIsIG5lLCBwICogMiArIDIpOwoJCWRbcF0gPSBtYXgoZFtwICogMiArIDFdLCBkW3AgKiAyICsgMl0pOwoJfQoKCXZvaWQgc2V0KGludCBhLCBsbCB4KXsKCQlzZXR3KGEsIHgsIDAsIG4sIDApOwoJfQoKCWxsIGdldHcoaW50IGEsIGludCBuYiwgaW50IG5lLCBpbnQgcCl7CgkJaWYgKGEgPCBuYiB8fCBuZSA8PSBhKSByZXR1cm4gZFtwXTsKCQlpZiAobmUgLSBuYiA9PSAxKSByZXR1cm4gLTE7CgkJcmV0dXJuIG1heChnZXR3KGEsIG5iLCAobmIgKyBuZSkgLyAyLCBwICogMiArIDEpLCBnZXR3KGEsIChuYiArIG5lKSAvIDIsIG5lLCBwICogMiArIDIpKTsKCX0KCglsbCBnZXQoaW50IGEpewoJCXJldHVybiBnZXR3KGEsIDAsIG4sIDApOwoJfQoKCWxsIGFsbCgpewoJCXJldHVybiBkWzBdOwoJfQp9OwoKY2xhc3Mgc2VnewpwdWJsaWM6CgljbGFzcyBub2RlewoJcHVibGljOgoJCWxsIG07CgkJbGwgYTsKCX07CgoJbm9kZSBuYWRkKG5vZGUgYSwgbGwgeCl7CgkJYS5hICs9IHg7CgkJYS5tICs9IHg7CgkJcmV0dXJuIGE7Cgl9CgoJbm9kZSB1bml0KG5vZGUgYSwgbm9kZSBiKXsKCQlub2RlIHc7CgkJdy5hID0gMDsKCQl3Lm0gPSBtYXgoYS5tLCBiLm0pOwoJCXJldHVybiB3OwoJfQoKCWludCBuOwoJbm9kZSogZDsKCgl2b2lkIGluaXQoaW50IG53KXsKCQlmb3IgKG4gPSAxOyBuIDw9IG53OyBuICo9IDIpe30KCQlkID0gbmV3IG5vZGVbbiAqIDJdOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbiAqIDI7IGkrKyl7CgkJCWRbaV0uYSA9IDA7CgkJCWRbaV0ubSA9IDA7CgkJfQoJfQoKCXZvaWQgYWRkdyhpbnQgYSwgbGwgeCwgaW50IG5iLCBpbnQgbmUsIGludCBwKXsKCQlpZiAobmUgPD0gYSkgcmV0dXJuOwoJCWlmIChhIDw9IG5iKXsKCQkJZFtwXSA9IG5hZGQoZFtwXSwgeCk7CgkJCXJldHVybjsKCQl9CgkJZFtwICogMiArIDFdID0gbmFkZChkW3AgKiAyICsgMV0sIGRbcF0uYSk7CgkJZFtwICogMiArIDJdID0gbmFkZChkW3AgKiAyICsgMl0sIGRbcF0uYSk7CgkJYWRkdyhhLCB4LCBuYiwgKG5iICsgbmUpIC8gMiwgcCAqIDIgKyAxKTsKCQlhZGR3KGEsIHgsIChuYiArIG5lKSAvIDIsIG5lLCBwICogMiArIDIpOwoJCWRbcF0gPSB1bml0KGRbcCAqIDIgKyAxXSwgZFtwICogMiArIDJdKTsKCX0KCgl2b2lkIGFkZChpbnQgYSwgbGwgeCl7CgkJYWRkdyhhLCB4LCAwLCBuLCAwKTsKCX0KCglsbCBnZXR3KGludCBhLCBpbnQgbmIsIGludCBuZSwgaW50IHApewoJCWlmIChhIDwgbmIgfHwgbmUgPD0gYSkgcmV0dXJuIGRbcF0ubTsKCQlpZiAobmUgLSBuYiA9PSAxKSByZXR1cm4gLTE7CgkJZFtwICogMiArIDFdID0gbmFkZChkW3AgKiAyICsgMV0sIGRbcF0uYSk7CgkJZFtwICogMiArIDJdID0gbmFkZChkW3AgKiAyICsgMl0sIGRbcF0uYSk7CgkJZFtwXS5hID0gMDsKCQlyZXR1cm4gbWF4KGdldHcoYSwgbmIsIChuYiArIG5lKSAvIDIsIHAgKiAyICsgMSksIGdldHcoYSwgKG5iICsgbmUpIC8gMiwgbmUsIHAgKiAyICsgMikpOwoJfQoKCWxsIGdldChpbnQgYSl7CgkJcmV0dXJuIGdldHcoYSwgMCwgbiwgMCk7Cgl9Cn07CgpjbGFzcyBzZWcyewpwdWJsaWM6CgliaXQgYjsKCXNlZyBzOwoKCXZvaWQgaW5pdChpbnQgbil7CgkJYi5pbml0KG4pOwoJCXMuaW5pdChuKTsKCX0KCgl2b2lkIGFkZDEoaW50IGEsIGxsIHgpewoJCXMuYWRkKGEsIHgpOwoJCXMuYWRkKGEgKyAxLCAteCk7Cgl9CgoJdm9pZCBhZGQyKGludCBhLCBsbCB4KXsKCQliLmFkZChhLCB4KTsKCQlzLmFkZChhLCB4KTsKCX0KCglsbCBnZXQoaW50IGEpewoJCWxsIHcxID0gcy5nZXQoYSk7CgkJbGwgdzIgPSBiLnN1bShhKTsKCQlyZXR1cm4gdzEgLSB3MjsKCX0KfTsKCmNsYXNzIHBvaW50ewpwdWJsaWM6CglpbnQgbywgb2IxLCBvYjI7CglpbnQgZGU7CgoJaW50IG47CglsbCogbTE7CglsbCogbTI7CgoJcm1xKiByOwoJc2VnMiBzMSwgczI7CgoJdm9pZCBpbml0KGludCBudyl7CgkJbiA9IG53OwoJCW0xID0gbmV3IGxsW25dOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSBtMVtpXSA9IDA7CgkJbTIgPSBuZXcgbGxbbl07CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIG0yW2ldID0gMDsKCQlyID0gbmV3IHJtcVtuXTsKCQlzMS5pbml0KG4pOwoJCXMyLmluaXQobik7Cgl9CgoJdm9pZCBzZXQxKGludCBiMSwgaW50IGIyLCBsbCB4KXsKCQlyW2IxXS5zZXQoYjIsIHgpOwoJCWxsIHcgPSByW2IxXS5hbGwoKTsKCQlzMS5hZGQxKGIxLCB3IC0gbTFbYjFdKTsKCQlzMi5hZGQxKG4gLSAxIC0gYjEsIHcgLSBtMVtiMV0pOwoJCW0xW2IxXSA9IHc7Cgl9CgoJdm9pZCBzZXQyKGludCBiLCBsbCB4KXsKCQlzMS5hZGQyKGIsIHggLSBtMltiXSk7CgkJczIuYWRkMihuIC0gYiwgeCAtIG0yW2JdKTsKCQltMltiXSA9IHg7Cgl9CgoJbGwgYWxsKCl7CgkJcmV0dXJuIHMxLmdldCgwKTsKCX0KCglsbCBnZXQoaW50IGIxLCBpbnQgYjIpewoJCWxsIHcxID0gczEuZ2V0KGIxKTsKCQlsbCB3MiA9IHMyLmdldChuIC0gMSAtIGIxKTsKCQlsbCB3MyA9IHJbYjFdLmdldChiMik7CgkJcmV0dXJuIG1heChtYXgodzEsIHcyKSwgdzMpOwoJfQoKCWxsIHRvdChpbnQgYSl7CgkJcmV0dXJuIHMxLmIuc3VtKGEpOwoJfQp9OwoKY2xhc3Mgcm5vZGV7CnB1YmxpYzoKCWludCBvOwoJdmVjdG9yPGludD4gazsKCWludCBzLCBzYjsKCWludCBrbSwga21iOwp9OwoKcm5vZGUgbm5bNTU1NTU1XTsKcG9pbnQgaGxwWzU1NTU1NV07CmludCBobHBuOwoKaW50IGRmczEoaW50IG4pewoJaW50IGwgPSBubltuXS5rLnNpemUoKTsKCW5uW25dLmttID0gMDsKCWludCBhbGwgPSAwOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspewoJCWludCB3ID0gZGZzMShubltuXS5rW2ldKTsKCQlpZiAobm5bbl0ua20gPCB3KXsKCQkJbm5bbl0ua20gPSB3OwoJCQlubltuXS5rbWIgPSBpOwoJCX0KCQlhbGwgKz0gdzsKCX0KCXJldHVybiBhbGwgKyAxOwp9Cgp2b2lkIGRmczIoaW50IG4sIGludCBzLCBpbnQgc2IpewoJbm5bbl0ucyA9IHM7CglubltuXS5zYiA9IHNiOwoJaW50IGwgPSBubltuXS5rLnNpemUoKTsKCWlmIChsID09IDApewoJCWhscFtzXS5pbml0KHNiICsgMSk7CgkJaGxwW3NdLnJbc2JdLmluaXQoMSk7Cgl9CgllbHNlewoJCWludCB3ID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IGw7IGkrKyl7CgkJCWlmIChpID09IG5uW25dLmttYikgZGZzMihubltuXS5rW2ldLCBzLCBzYiArIDEpOwoJCQllbHNlewoJCQkJaGxwW2hscG5dLm8gPSBzOwoJCQkJaGxwW2hscG5dLm9iMSA9IHNiOwoJCQkJaGxwW2hscG5dLm9iMiA9IHcrKzsKCQkJCWRmczIobm5bbl0ua1tpXSwgaGxwbisrLCAxKTsKCQkJfQoJCX0KCQlobHBbc10ucltzYl0uaW5pdChsKTsKCX0KfQoKdm9pZCBobCgpewoJZGZzMSgwKTsKCWhscG4gPSAxOwoJaGxwWzBdLm8gPSAtMTsKCWRmczIoMCwgMCwgMCk7Cn0KCmNsYXNzIHF1ZXJ5ewpwdWJsaWM6CglpbnQgczsKCWludCBhOwoJbGwgYzsKfTsKCnF1ZXJ5IHF1WzU1NTU1NV07Cgp2b2lkIHF1MTIoaW50IGEsIGxsIHgpewoJaW50IG5vdyA9IG5uW2FdLnM7CglobHBbbm93XS5zZXQyKG5uW2FdLnNiLCB4KTsKCWludCBiMSA9IGhscFtub3ddLm9iMTsKCWludCBiMiA9IGhscFtub3ddLm9iMjsKCWxsIGFsbCA9IGhscFtub3ddLmFsbCgpOwoJbm93ID0gaGxwW25vd10ubzsKCXdoaWxlIChub3cgPj0gMCl7CgkJaGxwW25vd10uc2V0MShiMSwgYjIsIGFsbCk7CgkJYjEgPSBobHBbbm93XS5vYjE7CgkJYjIgPSBobHBbbm93XS5vYjI7CgkJYWxsID0gaGxwW25vd10uYWxsKCk7CgkJbm93ID0gaGxwW25vd10ubzsKCX0KfQoKbGwgcXUzKGludCBhKXsKCWludCBub3cgPSBublthXS5zOwoJbGwgbWEgPSBobHBbbm93XS5nZXQobm5bYV0uc2IsIC0xKTsKCWxsIGFsbCA9IGhscFtub3ddLnRvdChublthXS5zYik7CglpbnQgYjEgPSBobHBbbm93XS5vYjE7CglpbnQgYjIgPSBobHBbbm93XS5vYjI7Cglub3cgPSBobHBbbm93XS5vOwoJd2hpbGUgKG5vdyA+PSAwKXsKCQltYSA9IG1heChtYSwgYWxsICsgaGxwW25vd10uZ2V0KGIxLCBiMikpOwoJCWFsbCArPSBobHBbbm93XS50b3QoYjEpOwoJCWIxID0gaGxwW25vd10ub2IxOwoJCWIyID0gaGxwW25vd10ub2IyOwoJCW5vdyA9IGhscFtub3ddLm87Cgl9CglyZXR1cm4gbWE7Cn0KCmludCBtYWluKCl7CglpbnQgbjsKCXNjYW5mKCIlZCIsICZuKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSBzY2FuZigiJWQlZCVsbGQiLCAmcXVbaV0ucywgJnF1W2ldLmEsICZxdVtpXS5jKTsKCWludCBhbGxrID0gMTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKCQlpZiAocXVbaV0ucyA9PSAxKXsKCQkJbm5bYWxsa10ubyA9IHF1W2ldLmE7CgkJCW5uW3F1W2ldLmFdLmsucHVzaF9iYWNrKGFsbGsrKyk7CgkJfQoJfQoJaGwoKTsKCWxvbmcgYW13ID0gMTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKCQlzd2l0Y2ggKHF1W2ldLnMpewoJCWNhc2UgMToKCQkJcXUxMihhbXcrKywgcXVbaV0uYyk7CgkJCWJyZWFrOwoJCWNhc2UgMjoKCQkJcXUxMihxdVtpXS5hLCBxdVtpXS5jKTsKCQkJYnJlYWs7CgkJY2FzZSAzOgoJCQlwcmludGYoIiVsbGRcbiIsIHF1MyhxdVtpXS5hKSk7CgkJCWJyZWFrOwoJCX0KCX0KCXJldHVybiAwOwp9Cg==