#include <algorithm>
#include <cassert>
#include <iostream>
#include <cassert>
#include <vector>
#define endl '\n'
using namespace std;
struct Virsune {
int pirmine_pozicija;
pair<int, int> atsakinga;
vector<int> vaikai;
};
int N, S;
vector<Virsune> priklausomybiu_medis;
vector<int> segmentuotas_medis;
void rasti_atsakingumo_rezius(int virsune, int &atsakingumo_pradzia) {
Virsune &v = priklausomybiu_medis[virsune];
v.atsakinga.first = atsakingumo_pradzia;
atsakingumo_pradzia += 1;
for (int vaikas: v.vaikai) {
rasti_atsakingumo_rezius(vaikas, atsakingumo_pradzia);
}
v.atsakinga.second = atsakingumo_pradzia - 1;
#ifndef EVAL
cerr << "Virsune " << virsune << " su pozicija " << v.pirmine_pozicija
<< " atsakinga uz [" << v.atsakinga.first
<< "; " << v.atsakinga.second << "]" << endl;
#endif
}
void rasti_atsakingumo_rezius(int virsune) {
int atsakingumo_pradzia = 1;
rasti_atsakingumo_rezius(virsune, atsakingumo_pradzia);
}
int saugi_segmentuoto_medzio_reiksme(int pozicija) {
return pozicija < S ? segmentuotas_medis[pozicija] : 0;
}
void keisti_segmentuotame_medyje(int pozicija, int nauja_reiksme) {
int indeksas = (S + 1) / 2 + pozicija - 1;
assert(segmentuotas_medis[indeksas] <= nauja_reiksme);
segmentuotas_medis[indeksas] = nauja_reiksme;
for (indeksas = indeksas / 2 /* pradedam nuo indekso tevinės viršūnės */;
indeksas /* kol tėvinė viršūnė egzistuoja */;
indeksas = indeksas / 2 /* lipam į kitą tėvinę viršūnę */) {
// Viršūnės reikšmė -- maksimumas tarp vaikinių viršūnių.
segmentuotas_medis[indeksas] = max(
saugi_segmentuoto_medzio_reiksme(indeksas * 2),
saugi_segmentuoto_medzio_reiksme(indeksas * 2 + 1));
}
}
int rasti_maksimuma_tarp(int virsune, int virsune_pradzia, int virsune_pabaiga,
int intervalo_pradzia, int intervalo_pabaiga) {
// Višūnė pilnai atsakinga už intervalo dalį.
if (intervalo_pradzia <= virsune_pradzia &&
virsune_pabaiga <= intervalo_pabaiga) {
return segmentuotas_medis[virsune];
}
// Viršūnė yra neatsakinga už intervalo reikšmes.
if (intervalo_pabaiga <= virsune_pradzia ||
virsune_pabaiga <= intervalo_pradzia) {
return 0;
}
// Viršūnė atsakinga už dalį reikšmių.
const int virsune_intervalo_ilgis = virsune_pabaiga - virsune_pradzia + 1;
return max(
// Kairiojo vaiko reikšmė.
rasti_maksimuma_tarp(virsune * 2,
virsune_pradzia,
virsune_pradzia + virsune_intervalo_ilgis / 2,
intervalo_pradzia, intervalo_pabaiga),
// Dešiniojo vaiko reikšmė.
rasti_maksimuma_tarp(virsune * 2 + 1,
virsune_pradzia + virsune_intervalo_ilgis / 2,
virsune_pabaiga,
intervalo_pradzia, intervalo_pabaiga)
);
}
int rasti_maksimuma_tarp(const pair<int, int> &intervalas) {
return rasti_maksimuma_tarp(1, 1, S / 2 + 1,
intervalas.first, intervalas.second + 1);
}
void atspausdinti_segmentuota_medi() {
for (int i : segmentuotas_medis) {
cerr << " " << i;
}
cerr << endl;
}
void atspausdinti_pozicijas() {
cerr << "{";
for (int i = 1; i <= N; i += 1) {
cerr << (i == 1 ? "" : ", ")
<< i << ": "
<< rasti_maksimuma_tarp(priklausomybiu_medis[i].atsakinga);
}
cerr << "}" << endl;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> N;
priklausomybiu_medis.resize(N + 1);
for (int i = 1; i <= N; i += 1) {
cin >> priklausomybiu_medis[i].pirmine_pozicija;
}
for (int i = 1; i <= N - 1; i += 1) {
int turi_buti_pries;
cin >> turi_buti_pries;
priklausomybiu_medis[turi_buti_pries].vaikai.push_back(i);
}
rasti_atsakingumo_rezius(N);
for (S = 1; S < N; S *= 2);
S = 2 * S;
segmentuotas_medis.resize(S);
for (int i = 1; i <= N; i += 1) {
keisti_segmentuotame_medyje(
priklausomybiu_medis[i].atsakinga.first,
priklausomybiu_medis[i].pirmine_pozicija);
}
#ifndef EVAL
cerr << "Segmentuotame medyje po jo inicilizavimo:";
atspausdinti_segmentuota_medi();
cerr << "Pozicijos: ";
atspausdinti_pozicijas();
#endif
int uzklausos;
cin >> uzklausos;
while (uzklausos--) {
string uzklausa;
int lektuvas;
cin >> uzklausa >> lektuvas;
const int lektuvo_pozicija =
rasti_maksimuma_tarp(priklausomybiu_medis[lektuvas].atsakinga);
if (uzklausa == "I") {
cout << lektuvo_pozicija << endl;
} else if (uzklausa == "P") {
int pastumpti;
cin >> pastumpti;
keisti_segmentuotame_medyje(
priklausomybiu_medis[lektuvas].atsakinga.first,
lektuvo_pozicija + pastumpti);
#ifndef EVAL
cerr << "Segmentuotame medyje po pakeitimo:";
atspausdinti_segmentuota_medi();
cerr << "Visos pozicijos po pakeitimo: ";
atspausdinti_pozicijas();
#endif
}
}
return 0;
}
