RT,思路是第一篇题解的。

// Problem: P9168 [省选联考 2023] 人员调度
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9168
// Memory Limit: 512 MB
// Time Limit: 5000 ms

#include<bits/stdc++.h>
#define mp make_pair
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define G(i,x) for(int i=start[x];i;i=Next[i])
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define mid ((L+R)>>1)
#define ins emplace
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;using ll=long long;using pii=pair<int,int>;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<21];
int read() {
	int s=0,w=0;char ch=getchar();
	while(ch<'0'||ch>'9') w|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return w?-s:s;
}
const int N=1e5+5,M=N<<1,N4=N<<2,M4=N<<2;
const ll inf=0x7f7f7f7f7f7f;
int sid,n,m,k,cnt,u[M],v[M],start[N],Next[M],fa[N],dfn[N],dfx[N],tot,son[N],top[N],siz[N];
void add(int x,int y) {u[++cnt]=x;v[cnt]=y;Next[cnt]=start[x];start[x]=cnt;}
void Add(int x,int y) {add(x,y);add(y,x);}
void dfs(int x) {
	siz[x]=1;
	G(i,x) if(v[i]^fa[x]) {
		fa[v[i]]=x;dfs(v[i]);
		siz[x]+=siz[v[i]];
		if(siz[v[i]]>siz[son[x]]) son[x]=v[i];
	}
}
void dfs2(int x,int tp) {
	dfn[x]=++tot;dfx[tot]=x;top[x]=tp;
	if(son[x]) dfs2(son[x],tp);
	G(i,x) if(v[i]^fa[x]&&v[i]^son[x]) dfs2(v[i],v[i]);
}
struct S1 {
	int mi[N4],tg[N4];
	void up(int d) {mi[d]=min(mi[l(d)],mi[r(d)]);}
	void ad(int d,int x) {mi[d]+=x;tg[d]+=x;}
	void down(int d) {if(tg[d]) ad(l(d),tg[d]),ad(r(d),tg[d]),tg[d]=0;}
	void build(int L,int R,int d) {
		if(L==R) return mi[d]=siz[dfx[L]],void();
		build(L,mid,l(d));build(mid+1,R,r(d));up(d);
	}
	void mo(int l,int r,int x,int L,int R,int d) {
		if(R<l||r<L) return;if(l<=L&&R<=r) return ad(d,x);
		down(d);mo(l,r,x,L,mid,l(d));mo(l,r,x,mid+1,R,r(d));up(d);
	}
	int q(int l,int r,int L,int R,int d) {
		if(R<l||r<L||mi[d]>0) return 0;
		if(l<=L&&R<=r) {
			if(L==R) return mi[d]==0?L:0;
			return down(d),mi[r(d)]==0?q(l,r,mid+1,R,r(d)):q(l,r,L,mid,l(d));
		}
		return down(d),max(q(l,r,L,mid,l(d)),q(l,r,mid+1,R,r(d)));
	}
} T1;
struct S2 {
	using pii=pair<ll,int>;
	multiset<pii> s[N4];
	pii mi[N4];ll sum[N4];
	void up(int d) {mi[d]=min(mi[l(d)],mi[r(d)]);sum[d]=sum[l(d)]+sum[r(d)];}
	void build(int L,int R,int d) {
		if(L==R) return mi[d]=mp(inf,L),void();
		build(L,mid,l(d));build(mid+1,R,r(d));up(d);
	}
	void ins(int id,ll x,int L,int R,int d) {
		if(L==R) return s[d].ins(x,L),mi[d]=min(mi[d],mp(x,L)),sum[d]+=x,void();
		id<=mid?ins(id,x,L,mid,l(d)):ins(id,x,mid+1,R,r(d));up(d);
	}
	void del(int id,ll x,int L,int R,int d) {
		if(L==R) return s[d].erase(s[d].find(mp(x,id))),mi[d]=s[d].empty()?mp(inf,L):*s[d].begin(),sum[d]-=x,void();
		id<=mid?del(id,x,L,mid,l(d)):del(id,x,mid+1,R,r(d));up(d);
	}
	pii qmi(int l,int r,int L,int R,int d) {
		if(l<=L&&R<=r) return mi[d];
		if(R<l||r<L) return mp(inf,114514);
		return min(qmi(l,r,L,mid,l(d)),qmi(l,r,mid+1,R,r(d)));
	}
} T2;
struct S {int x,v,b,se;ll fi;} sta[M];int t;
void addp(int x,ll v) {
	int res=0,z=x;
	while(top[z]) {
		res=dfx[T1.q(dfn[top[z]],dfn[z],1,n,1)];
		if(res) break;
		z=fa[top[z]];
	}
	if(!res) {
		z=x;
		while(top[z]) {
			T1.mo(dfn[top[z]],dfn[z],-1,1,n,1);
			z=fa[top[z]];
		} T2.ins(dfn[x],v,1,n,1),sta[++t]={x,v,1,0,0};
	}
	else {
		// cerr<<"???\n";
		auto pi=T2.qmi(dfn[res],dfn[res]+siz[res]-1,1,n,1);
		if(pi.fi>v||pi.fi==v&&siz[x]<siz[dfx[pi.se]]) return sta[++t]={114514,1919810,114514,1919810,114514},void();
		T2.del(pi.se,pi.fi,1,n,1);T2.ins(dfn[x],v,1,n,1);sta[++t]={x,v,2,pi.se,pi.fi};
	}
}
void CtrlZ() {
	int x=sta[t].x,b=sta[t].b,se=sta[t].se;ll fi=sta[t].fi,v=sta[t].v;
	if(b==1) {
		int z=x;
		while(top[z]) {
			T1.mo(dfn[top[z]],dfn[z],1,1,n,1);
			z=fa[top[z]];
		} T2.del(dfn[x],v,1,n,1);
	} else if(b==2) {
		T2.ins(se,fi,1,n,1);T2.del(dfn[x],v,1,n,1);
	} t--;
}
ll res() {return T2.sum[1];}
ll ans[M],V[M],val;
int x,X[M],l,r,L[M],R[M];vector<pair<int,ll>> vec[M4];
void ins(int L,int R,int d) {
	if(l<=L&&R<=r) return vec[d].pb(x,val),void();
	if(R<l||r<L) return;
	ins(L,mid,l(d));ins(mid+1,R,r(d));
}
void HereWeGo(int L,int R,int d) {
	for(auto pi:vec[d]) addp(pi.fi,pi.se);
	if(L==R) ans[L]=res();
	else HereWeGo(L,mid,l(d)),HereWeGo(mid+1,R,r(d));
	for(auto pi:vec[d]) CtrlZ();
}
int main() {
	sid=read();n=read();k=read();m=read();
	F(i,2,n) Add(i,read());
	dfs(1);dfs2(1,1);T1.build(1,n,1);T2.build(1,n,1);
	F(i,1,k) X[i]=read(),V[i]=read(),L[i]=0,R[i]=m;
	F(i,1,m) switch(read()) {
		case 1:L[++k]=i;R[k]=m;X[k]=read();V[k]=read();break;
		case 2:R[read()]=i-1;break;
	}
	F(i,1,k) x=X[i],val=V[i],l=L[i],r=R[i],ins(0,m,1);
	HereWeGo(0,m,1);
	F(i,0,m) cout<<ans[i]<<' ';
	return 0; 
}