用的3log做法

只有 34 分，其他的全TLE

开的O2 + c++20也是这样

#include<bits/stdc++.h>
#define N 400005
#define ls (now<<1)
#define rs (now<<1|1)
#define inf 1000000000
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,q,sid,fa[N],st[N],et[N],siz[N],Ans;
struct per
{
	int x,v;
	bool operator<(per a)const
	{
		return v<a.v;
	}
}p[N];
per Min(per a,per b)
{
	if(a.v<b.v)return a;
	else return b; 
}
struct query
{
	int id,x,y;
}c[N];
stack<vector<query> > t;
stack<query> t2;
struct fig
{
	int to,next;
}k[N*2];int head[N],tot;
void add(int from,int to)
{
	k[++tot].to=to;
	k[tot].next=head[from];
	head[from]=tot;
}
vector<per> v[N];
void ins(int now,int l,int r,int ql,int qr,per p)
{
	if(l>=ql&&r<=qr)
	{
		v[now].push_back(p);
		return ;
	}
	int mid=(l+r)>>1;
	if(mid>=ql)ins(ls,l,mid,ql,qr,p);
	if(mid<qr)ins(rs,mid+1,r,ql,qr,p);
}
int son[N],dfn[N],cnt,top[N],id[N];
void dfs(int now)
{
	siz[now]=1;
	for(int i=head[now];i;i=k[i].next)
	{
		dfs(k[i].to);
		siz[now]+=siz[k[i].to];
		if(siz[son[now]]<siz[k[i].to])son[now]=son[k[i].to];
	}
}
void pf(int now,int tp)
{
	dfn[now]=++cnt;id[cnt]=now;
	top[now]=tp;
	if(son[now])pf(son[now],tp);
	for(int i=head[now];i;i=k[i].next)
	{
		if(k[i].to==son[now])continue;
		pf(k[i].to,k[i].to);
	}
}
struct tree
{
	int lz,mn;per w; 
	multiset<per> q;
}tr[N*4];
void up(int now)
{
	tr[now].mn=min(tr[ls].mn,tr[rs].mn);
	tr[now].w=Min(tr[ls].w,tr[rs].w);
}
void down(int now)
{
	if(tr[now].lz)
	{
		tr[ls].mn+=tr[now].lz;
		tr[ls].lz+=tr[now].lz;
		tr[rs].mn+=tr[now].lz;
		tr[rs].lz+=tr[now].lz;
	}
	tr[now].lz=0;
}
void build(int now,int l,int r)
{
	tr[now].mn=inf;tr[now].w=per{inf,inf};
	tr[now].q.insert(per{inf,inf});
	if(l==r)
	{
		tr[now].mn=siz[id[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r);
	up(now);
}
void midy(int now,int l,int r,int ql,int qr,int w)
{
	if(l>=ql&&r<=qr)
	{
		tr[now].mn+=w;
		tr[now].lz+=w;
		return ;
	}
	int mid=(l+r)>>1;down(now);
	if(mid>=ql)midy(ls,l,mid,ql,qr,w);
	if(mid<qr)midy(rs,mid+1,r,ql,qr,w);
	up(now);
}
int ans;
void find(int now,int l,int r)
{
	if(l==r)
	{
		ans=l;
		return ;
	}
	int mid=(l+r)>>1;down(now);
	if(tr[rs].mn==0)find(rs,mid+1,r);
	else find(ls,l,mid);
}
void getr(int now,int l,int r,int ql,int qr)
{
	if(ans)return ;
	if(l>=ql&&r<=qr)
	{ 
		if(tr[now].mn==0)find(now,l,r);
		return ;
	}
	int mid=(l+r)>>1;down(now);
	if(mid<qr)getr(rs,mid+1,r,ql,qr);
	if(mid>=ql)getr(ls,l,mid,ql,qr);
}
void sol(int a)
{
	ans=0;vector<query> v;
	while(a!=0)
	{
		getr(1,1,n,dfn[top[a]],dfn[a]);
		a=fa[top[a]];
		if(ans)break;
	}
}
per que(int now,int l,int r,int ql,int qr)
{
	if(l>=ql&&r<=qr)return tr[now].w;
	int mid=(l+r)>>1;per cnt=per{inf,inf};down(now);
	if(mid>=ql)cnt=Min(cnt,que(ls,l,mid,ql,qr));
	if(mid<qr)cnt=Min(cnt,que(rs,mid+1,r,ql,qr));
	return cnt;
}
void inst(int now,int l,int r,int x,per p)
{
	if(l==r)
	{
		tr[now].w=Min(tr[now].w,p);
		tr[now].q.insert(p);
		return ;
	}
	int mid=(l+r)>>1;down(now);
	if(mid>=x)inst(ls,l,mid,x,p);
	else inst(rs,mid+1,r,x,p);
	up(now); 
}
void del(int now,int l,int r,int x,per w)
{
	if(l==r)
	{
		tr[now].q.erase(tr[now].q.lower_bound(w));
		tr[now].w=*tr[now].q.begin(); 
		return ;
	}
	int mid=(l+r)>>1;down(now);
	if(mid>=x)del(ls,l,mid,x,w);
	else del(rs,mid+1,r,x,w);
	up(now); 
}
void sol(int a,int w)
{
	ans=0;vector<query> v;
	while(a!=0)
	{
		midy(1,1,n,dfn[top[a]],dfn[a],w);
		a=fa[top[a]];
	}
}
void run(int now,int l,int r)
{
	int num=0,awa=0;
	for(per i:v[now])
	{
		sol(i.x);
		if(ans)
		{
			per mn=que(1,1,n,ans,ans+siz[id[ans]]-1);
			if(mn.v<i.v)
			{
				del(1,1,n,dfn[mn.x],mn);sol(mn.x,1); 
				inst(1,1,n,dfn[i.x],i);sol(i.x,-1);
				Ans-=mn.v;
				Ans+=i.v;
				t2.push(query{1,mn.x,mn.v});
				t2.push(query{2,i.x,i.v});
				num+=2;
			}
		}
		else 
		{
			num++;
			Ans+=i.v;
			inst(1,1,n,dfn[i.x],i);sol(i.x,-1);
			t2.push(query{2,i.x,i.v});
		}
	}
	if(l==r)cout<<Ans<<" ";
	else
	{
		int mid=(l+r)>>1;
		run(ls,l,mid);
		run(rs,mid+1,r);
	}
	for(int j=1;j<=awa;j++)
	{
		vector<query> v=t.top();t.pop();
		for(query i:v)midy(1,1,n,i.id,i.x,i.y);
	}
	for(int i=1;i<=num;i++)
	{
		query x=t2.top();t2.pop();
		if(x.id==2)del(1,1,n,dfn[x.x],per{x.x,x.y}),Ans-=x.y,sol(x.x,1);
		else inst(1,1,n,dfn[x.x],per{x.x,x.y}),Ans+=x.y,sol(x.x,-1);
	}
}
signed main()
{
	sid=read();
	n=read();m=read();q=read();
	for(int i=2;i<=n;i++)fa[i]=read(),add(fa[i],i);
	for(int i=1;i<=m;i++)p[i].x=read(),p[i].v=read(),st[i]=1;
	for(int i=1;i<=q;i++)
	{
		c[i].id=read();c[i].x=read();
		if(c[i].id==1)
		{
			c[i].y=read();
			m++;
			p[m].x=c[i].x;
			p[m].v=c[i].y;
			st[m]=i+1;
		}
		if(c[i].id==2)et[c[i].x]=i;
	}
	q++;
	for(int i=1;i<=m;i++)
	{
		if(et[i]==0)et[i]=q;
		ins(1,1,q,st[i],et[i],p[i]);
	}
	dfs(1);pf(1,1);build(1,1,n);
	run(1,1,q);
	return 0;
}