去年省选的时候还不会霍尔定理，想到了线段树分治想不了贪心。今年看感觉挺傻逼的。
先线段树分治，把删除操作扔了。如果我们要知道一个人最后扔到哪里，那就是一个费用流问题，不太可能解决，考虑用霍尔定理刻画这个东西，我们发现，最后一个人的集合能匹配上当且仅当：
计 \(u\) 子树里有 \(p_u\) 个人，那么满足 \(\forall u,siz_u-p_u \ge 0\)。
每次如果加入一个人，需要满足这个人到根的路径上所有 \(siz_u-p_u>0\)。如果满足可以直接加，否则，我们必须换掉一个人，设 \(u\) 到根路径上最深的 \(siz_u-p_u=0\) 的点为 \(w\)，则换掉的点必须在 \(w\) 子树内。拿两颗线段树做这事就行。
复杂度 \(n\log^3{n}\)。这里默认 \(n,q\) 同阶。
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
int n,m,k,sid,fat[maxn],tot,lt[maxn],rt[maxn];
ll x[maxn<<1],v[maxn<<1],ans;
int p[maxn];
vector<int> mdi[maxn<<2];
vector<int> G[maxn];
ll mn[maxn<<2],siz[maxn],son[maxn],top[maxn],dfn[maxn],times,seq[maxn],tag[maxn<<2];
set< pair<ll,int> >qu[maxn<<2];
ll mnt[maxn<<2],idt[maxn<<2];
inline void Pushup(int i)
{
if(mnt[i<<1]<mnt[i<<1|1])
mnt[i]=mnt[i<<1],idt[i]=idt[i<<1];
else
mnt[i]=mnt[i<<1|1],idt[i]=idt[i<<1|1];
}
inline void addp(int i,int l,int r,int p,int v,int id)
{
if(l==r)
{
qu[i].insert({v,id});
if(qu[i].empty())mnt[i]=1e9,idt[i]=0;
else
mnt[i]=(*qu[i].begin()).first,idt[i]=(*qu[i].begin()).second;
return;
}
int mid=l+r>>1;
if(p<=mid)addp(i<<1,l,mid,p,v,id);
if(p>mid)addp(i<<1|1,mid+1,r,p,v,id);
Pushup(i);
}
inline void clrp(int i,int l,int r,int p,int v,int id)
{
if(l==r)
{
assert(qu[i].find({v,id})!=qu[i].end());
qu[i].erase({v,id});
if(qu[i].empty())mnt[i]=1e9,idt[i]=0;
else
mnt[i]=(*qu[i].begin()).first,idt[i]=(*qu[i].begin()).second;
return;
}
int mid=l+r>>1;
if(p<=mid)clrp(i<<1,l,mid,p,v,id);
if(p>mid)clrp(i<<1|1,mid+1,r,p,v,id);
Pushup(i);
}
pair<int,int> tquery(int i,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return {mnt[i],idt[i]};
int mid=l+r>>1;
if(R<=mid)return tquery(i<<1,l,mid,L,R);
if(L>mid)return tquery(i<<1|1,mid+1,r,L,R);
return min(tquery(i<<1,l,mid,L,R),tquery(i<<1|1,mid+1,r,L,R));
}
inline void pushtg(int i,int v)
{
mn[i]+=v;
tag[i]+=v;
}
inline void pushdown(int i)
{
if(!tag[i])return;
pushtg(i<<1,tag[i]);
pushtg(i<<1|1,tag[i]);
tag[i]=0;
}
inline void update(int i,int l,int r,int L,int R,int v)
{
if(L<=l&&r<=R){pushtg(i,v);return;}
int mid=l+r>>1;pushdown(i);
if(L<=mid)update(i<<1,l,mid,L,R,v);
if(R>mid)update(i<<1|1,mid+1,r,L,R,v);
mn[i]=min(mn[i<<1],mn[i<<1|1]);
}
inline int query(int i,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return mn[i];
int mid=l+r>>1;pushdown(i);
if(R<=mid)return query(i<<1,l,mid,L,R);
if(L>mid)return query(i<<1|1,mid+1,r,L,R);
return min(query(i<<1,l,mid,L,R),query(i<<1|1,mid+1,r,L,R));
}
inline int findz(int i,int l,int r,int L,int R)
{
if(r<L||l>R)return 0;
if(mn[i]>0)return 0;
if(l==r)return l;
int mid=l+r>>1;pushdown(i);
int ret=0;
if(R>mid)ret=findz(i<<1|1,mid+1,r,L,R);
if(ret)return ret;
return findz(i<<1,l,mid,L,R);
}
inline void updrt(int x,int v)
{
while(x)
{
update(1,1,n,dfn[top[x]],dfn[x],v);
x=fat[top[x]];
}
}
inline int qryrt(int x)
{
int ret=1e9;
while(x)
{
int now=query(1,1,n,dfn[top[x]],dfn[x]);
ret=min(ret,now);
if(ret==0)return seq[findz(1,1,n,dfn[top[x]],dfn[x])];
x=fat[top[x]];
}
return 0;
}
inline void build(int i,int l,int r)
{
mnt[i]=1e9;
if(l==r)
{
mn[i]=siz[seq[l]];
return;
}
int mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
mn[i]=min(mn[i<<1],mn[i<<1|1]);
}
inline void Modify(int i,int l,int r,int L,int R,int id)
{
if(L<=l&&r<=R){mdi[i].push_back(id);return;}
int mid=l+r>>1;
if(L<=mid)Modify(i<<1,l,mid,L,R,id);
if(R>mid)Modify(i<<1|1,mid+1,r,L,R,id);
}
void topdfs(int u,int topf)
{
top[u]=topf;
seq[dfn[u]=++times]=u;
if(!son[u])return;
topdfs(son[u],topf);
for(int v:G[u])
if(v!=son[u])
topdfs(v,v);
}
ll Ans[maxn];
inline void dfs(int i,int l,int r)
{
vector<int> opr;
for(int id:mdi[i])
{
int mnp=qryrt(x[id]);
if(!mnp)
{
ans+=v[id];
opr.push_back(id);
updrt(x[id],-1);
addp(1,1,n,dfn[x[id]],v[id],id);
}
else
{
ll tmn,td;
tie(tmn,td)=tquery(1,1,n,dfn[mnp],dfn[mnp]+siz[mnp]-1);
if(tmn<v[id])
{
int pos=x[td];
ans-=tmn;
ans+=v[id];
updrt(pos,1);
clrp(1,1,n,dfn[pos],v[td],td);
opr.push_back(id);
opr.push_back(-td);
updrt(x[id],-1);
addp(1,1,n,dfn[x[id]],v[id],id);
}
}
}
if(l==r)
Ans[l]=ans;
else
{
int mid=l+r>>1;
dfs(i<<1,l,mid);
dfs(i<<1|1,mid+1,r);
}
reverse(opr.begin(),opr.end());
for(int id:opr)
{
if(id>0)ans-=v[id],updrt(x[id],1),clrp(1,1,n,dfn[x[id]],v[id],id);
else ans+=v[-id],updrt(x[-id],-1),addp(1,1,n,dfn[x[-id]],v[-id],-id);
}
}
int main()
{
cin>>sid;
cin>>n>>k>>m;
for(int i=2;i<=n;i++)
cin>>fat[i],G[fat[i]].push_back(i);
for(int i=1;i<=n;i++)siz[i]=1;
tot=k;
for(int i=1;i<=k;i++)
cin>>x[i]>>v[i],rt[i]=m;
for(int i=1;i<=m;i++)
{
int opt;
cin>>opt;
if(opt==1)
{
++tot;
cin>>x[tot]>>v[tot];
lt[tot]=i;
rt[tot]=m;
}
else
{
int id;
cin>>id;
rt[id]=i-1;
}
}
for(int i=n;i>=2;i--)
{
siz[fat[i]]+=siz[i];
if(siz[son[fat[i]]]<siz[i])son[fat[i]]=i;
}
topdfs(1,1);
for(int i=1;i<=tot;i++)
Modify(1,0,m,lt[i],rt[i],i);
build(1,1,n);
dfs(1,0,m);
for(int i=0;i<=m;i++)
cout<<Ans[i]<<' ';
cout<<'\n';
return 0;
}