这个题可以单 $\log$。

前面忘了。

默认大家会 $\log^3$ 做法。考虑我们是怎么加入一个元素的：把他加入某个数据结构，然后找到最深的子树内元素个数大于子树大小的节点，删除子树内最小的元素。

注意到我们只修改了两个元素，而且答案显然和加入顺序没关系，那么理论上我们删除一个在答案里的元素的时候也只会加回来一个。我们维护一个不在答案里的元素的数据结构，删除一个元素后显然只有所有祖先都没满的元素才能加回来，我们加回来最大的元素。

我们考虑在静态 toptree 上维护这个东西。我们维护在/不在界点路径上的 子树大小减子树元素个数 的最小值（这个肯定需要非负），同时维护是否取到两个最小值的四个状态的最大元素，这个显然是可以合并的。对于加入操作，我们可以顺便维护两个最深的最小值位置，然后在 DFS 序上使用线段树维护最小的已加入的元素。

这样我们就做到了单 $\log$ 并且还是在线的。code

#include <bits/stdc++.h>
using namespace std;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second

constexpr int N = 1e5+5, inf = numeric_limits<int>::max();

int tc,n,m,q;
int f[N];
vector<int> G[N];
ll ans;

int pos[N<<1],val[N<<1];
int vmin(int x,int y){
    return val[x]<val[y]?x:y;
}
int vmax(int x,int y){
    return val[x]>val[y]?x:y;
}
int maxmin(int x,int y,int a,int b){
    return max(x<=y?a:0,y<=x?b:0);
}
struct node{
    int sum;
    int mnC,mnS;
    int lowC,lowS;
    int pup[2][2];
}tr[N<<1];
int rt;
node rake(const node &a,const node &b){
    node ans{};
    ans.sum=a.sum+b.sum;
    ans.mnC=a.mnC;
    ans.mnS=min({a.mnS,b.mnC,b.mnS});
    ans.lowC=a.lowC;
    ans.lowS=maxmin(a.mnS,b.mnS,a.lowS,b.lowS);
    ans.lowS=maxmin(min(a.mnS,b.mnS),b.mnC,ans.lowS,b.lowC);
    rep(x,0,1)rep(y,0,1){
        int &o=ans.pup[x][y&&a.mnS<=min(b.mnC,b.mnS)];
        o=vmax(o,a.pup[x][y]);
    }
    rep(x,0,1)rep(y,0,1){
        int &o=ans.pup[0][(x&&b.mnC<=ans.mnS)||(y&&b.mnS<=ans.mnS)];
        o=vmax(o,b.pup[x][y]);
    }
    return ans;
}
node compress(const node &a,const node &b){
    node ans{};
    ans.sum=a.sum+b.sum;
    ans.mnC=min(a.mnC+b.sum,b.mnC);
    ans.mnS=min(a.mnS,b.mnS);
    ans.lowC=maxmin(a.mnC+b.sum,b.mnC,a.lowC,b.lowC);
    ans.lowS=maxmin(a.mnS,b.mnS,a.lowS,b.lowS);
    rep(x,0,1)rep(y,0,1){
        int &o=ans.pup[x&&a.mnC+b.sum<=b.mnC][y&&a.mnS<=b.mnS];
        o=vmax(o,a.pup[x][y]);
    }
    rep(x,0,1)rep(y,0,1){
        int &o=ans.pup[x||a.mnC+b.sum<=b.mnC][y&&b.mnS<=a.mnS];
        o=vmax(o,b.pup[x][y]);
    }
    return ans;
}

int sz[N],hs[N],dfn[N],tick;
void dfs1(int u){
    sz[u]=1,dfn[u]=++tick;
    for(auto v:G[u]){
        dfs1(v),sz[u]+=sz[v];
        if(sz[v]>sz[hs[u]])hs[u]=v;
    }
}
int ls[N<<1],rs[N<<1],fa[N<<1],tot;
bool typ[N<<1];
int mer(int u,int v,bool t){
    ls[++tot]=u,rs[tot]=v;
    fa[u]=fa[v]=tot,typ[tot]=t;
    return tr[tot]=(t?compress:rake)(tr[u],tr[v]),tot;
}
using pii = pair<int,int>;
using vit = vector<pii>::iterator;
int dc(vit l,vit r,bool t){
    if(l+1==r)return l->fir;
    int sum=0;vit mid=l;
    for(vit x=l;x!=r;++x)sum+=x->sec;
    while(mid+1!=r&&sum>0)sum-=mid->sec<<1,++mid;
    return mer(dc(l,mid,t),dc(mid,r,t),t);
}
int dfs2(int u){
    vector<int> ch;
    int x=u;while(hs[x])ch.push_back(x),x=hs[x];
    vector<pii> rt{{u,1}};
    for(auto x:ch){
        vector<pii> vc{{hs[x],1}};
        for(auto y:G[x])if(y!=hs[x])vc.emplace_back(dfs2(y),sz[y]);
        rt.emplace_back(dc(allc(vc),0),sz[x]-sz[hs[x]]);
    }
    return dc(allc(rt),1);
}
set<pii> sI[N],sD[N];
void upd(int x){
    tr[x].mnC=tr[x].sum;
    tr[x].pup[1][0]=sD[x].rbegin()->sec;
    while(x=fa[x])tr[x]=(typ[x]?compress:rake)(tr[ls[x]],tr[rs[x]]);
}

namespace segt{
    pii tr[N<<1];
    void upd(int x){
        tr[x+n-1]=*sI[x].begin(),x+=n-1;
        while(x>>=1)tr[x]=min(tr[x<<1],tr[x<<1|1]);
    }
    pii qr(int l,int r){
        l+=n-1,r+=n-1;pii ans{inf,inf};
        while(l<=r){
            if( l&1)ans=min(ans,tr[l++]);
            if(~r&1)ans=min(ans,tr[r--]);
            l>>=1,r>>=1;
        }
        return ans;
    }
}
void ins(int x){
    ans+=val[x],--tr[pos[x]].sum,upd(pos[x]);
    sI[dfn[pos[x]]].emplace(val[x],x),segt::upd(dfn[pos[x]]);
    while(min(tr[rt].mnC,tr[rt].mnS)<0){
        int p=maxmin(tr[rt].mnC,tr[rt].mnS,tr[rt].lowC,tr[rt].lowS);
        int o=segt::qr(dfn[p],dfn[p]+sz[p]-1).sec;
        ans-=val[o],++tr[pos[o]].sum;
        sI[dfn[pos[o]]].erase({val[o],o}),segt::upd(dfn[pos[o]]);
        sD[pos[o]].emplace(val[o],o);
        upd(pos[o]);
    }
}
void del(int x){
    if(sD[pos[x]].count({val[x],x})){
        sD[pos[x]].erase({val[x],x});
        upd(pos[x]);return;
    }
    ans-=val[x],++tr[pos[x]].sum,upd(pos[x]);
    sI[dfn[pos[x]]].erase({val[x],x}),segt::upd(dfn[pos[x]]);
    while(true){
        int o=0;
        rep(x,0,1)rep(y,0,1)
            if((!x||tr[rt].mnC>0)&&(!y||tr[rt].mnS>0))o=vmax(o,tr[rt].pup[x][y]);
        if(!o)break;
        ans+=val[o],--tr[pos[o]].sum;
        sD[pos[o]].erase({val[o],o});
        sI[dfn[pos[o]]].emplace(val[o],o),segt::upd(dfn[pos[o]]);
        upd(pos[o]);
    }
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    cin>>tc>>n>>m>>q;
    rep(i,2,n)cin>>f[i],G[f[i]].push_back(i);
    dfs1(1);
    rep(i,1,n)tr[i].sum=tr[i].mnC=tr[i].sum=1,tr[i].mnS=1e9,tr[i].lowC=i;
    tot=n,rt=dfs2(1);
    rep(i,1,n)sI[i].emplace(inf,inf),sD[i].emplace(-inf,0),segt::upd(i);
    rep(i,1,m)cin>>pos[i]>>val[i],ins(i);cout<<ans;
    while(q--){
        int o;cin>>o;
        if(o==1)++m,cin>>pos[m]>>val[m],ins(m);
        else{int x;cin>>x;del(x);}
        cout<<' '<<ans;
    }
    cout<<'\n';
}