题意
给出一棵有根树，初始有一些员工在某些点上，一个点上可能有多个员工，每个员工都有一个能力值。
每个员工可以走到初始所在点的子树里的任何一个点，最后的贡献是每个点上的员工的能力值的最大值之和。
每一时刻所有员工都会回到原位置，同时可能会来一个新的员工或者开除一个现在还存在的员工，在每个时刻的操作完成后，合理安排员工的位置，最大化贡献值并输出。
所有东西的范围都是 \(10^5\)，时限 \(5\) 秒，空间限制 \(512\) MB。
题解
若一个员工是一个点能力值最大的员工，我们称其被使用。
先考虑没有任何修改怎么做。我们做一个 dfs，然后每个点维护一个 set，表示下方所有被使用员工的能力值，空的点的能力值为 \(0\)。
合并的时候使用启发式合并即可在 \(O(n\log^2 n)\) 的复杂度内算出答案。
现在考虑如果只会往里加人怎么做。可以发现，对于这个点祖先的子树来说，如果每个子树现在都不饱和，那么这个人可以找到一个点走过去；否则，我们必须要踢掉一个人才能被使用。
显然，我们总是应该踢掉能力值最小的员工，于是我们找到加入人的这个点子树饱和的最深的祖先，然后求出其内目前被使用的最小的员工，尝试踢掉它即可。
我们可以证明我们踢掉这个人之后总是能合理安排人员的分布，使得仍然填满整个子树的。这是因为，比方说 \(u\) 是最深的饱和的祖先，那么 \(u\) 一定往 \(x\) 所在子树派遣了一些人，此时我们扣掉了点 \(y\) 上的人，只需要把 \(u\) 往 \(x\) 子树里派遣的人改为派遣到 \(y\) 即可。
现在问题变成了，如何找到最深的饱和的祖先，以及子树内被使用员工的能力值的最小值。
对于第一个问题，我们考虑树剖+线段树，维护每个点的子树内还有多少空余的点，那么加入一个人就是根链减去 \(1\)，踢掉一个人就是根链增加 \(1\)。
对于第二个问题，考虑用 set 维护，初始在一个点的被使用员工的信息。然后线段树上的信息就是一个点的 set 的第一个值的信息，加入和删除一个人都只需要单点修改，查询子树信息的时候就是在线段树上区间查询。
若有删除操作，发现并不好做，考虑用线段树分治变为撤销，显然撤销操作是不困难的，用栈存储一下即可。
代码
点击查看代码
#include<bits/stdc++.h>
#define int long long
// #define ui unsigned int
// #define ll __int128
#define ull unsigned long long
#define N 200005
#define M 100005
#define K 20
// #define B 13331
#define mod 1000000007
#define pii pair<int,int>
#define x first
#define y second
#define pct __builtin_popcount
#define mpi make_pair
#define pi acos(-1)
#define inf 2e18
#define poly vector<int>
using namespace std;
int Id,Tc=1,n,k,m;
vector<int>e[N];
void add(int a,int b){e[a].push_back(b);
}
int dep[N],fa[N],siz[N],son[N],top[N];
int dfn[N],nw[N],idx;
set<pii>s[N];
void dfs1(int u,int f){dep[u]=dep[f]+1;fa[u]=f;siz[u]=1;for(auto v:e[u]){if(v==fa[u])continue;dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;}
}
void dfs2(int u,int f){top[u]=f;dfn[u]=++idx;nw[idx]=u;if(son[u])dfs2(son[u],f);for(auto v:e[u]){if(v==fa[u]||v==son[u])continue;dfs2(v,v);}
}
struct sgt1{struct node{int mn,pos,tag;}tr[N<<2];void pushup(int u){tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);if(tr[u<<1|1].mn<=tr[u<<1].mn)tr[u].pos=tr[u<<1|1].pos;else tr[u].pos=tr[u<<1].pos;}void build(int u,int l,int r){if(l==r){tr[u].mn=siz[nw[l]];tr[u].pos=l;return;}int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}void maketag(int u,int v){tr[u].mn+=v;tr[u].tag+=v;}void pushdown(int u){if(!tr[u].tag)return;maketag(u<<1,tr[u].tag);maketag(u<<1|1,tr[u].tag);tr[u].tag=0;}void modify(int u,int l,int r,int L,int R,int v){if(l>=L&&r<=R){maketag(u,v);return;}pushdown(u);int mid=l+r>>1;if(L<=mid)modify(u<<1,l,mid,L,R,v);if(R>mid)modify(u<<1|1,mid+1,r,L,R,v);pushup(u);}pii qry(int u,int l,int r,int L,int R){if(l>=L&&r<=R)return {tr[u].mn,tr[u].pos};pushdown(u);int mid=l+r>>1;if(R<=mid)return qry(u<<1,l,mid,L,R);else if(L>mid)return qry(u<<1|1,mid+1,r,L,R);else{auto ql=qry(u<<1,l,mid,L,R);auto qr=qry(u<<1|1,mid+1,r,L,R);int mn=min(ql.x,qr.x);int pos=(mn==qr.x?qr.y:ql.y);return {mn,pos};}}
}sgt1;
void modify_path(int a,int b,int c){while(top[a]!=top[b]){if(dep[top[a]]<dep[top[b]])swap(a,b);sgt1.modify(1,1,n,dfn[top[a]],dfn[a],c);a=fa[top[a]];}if(dep[a]<dep[b])swap(a,b);sgt1.modify(1,1,n,dfn[b],dfn[a],c);
}
pii qry_path(int a,int b){int res=inf,pos=-1;while(top[a]!=top[b]){if(dep[top[a]]<dep[top[b]])swap(a,b);auto cur=sgt1.qry(1,1,n,dfn[top[a]],dfn[a]);if(cur.x<res){res=cur.x;pos=cur.y;}a=fa[top[a]];}if(dep[a]<dep[b])swap(a,b);auto cur=sgt1.qry(1,1,n,dfn[b],dfn[a]);if(cur.x<res){res=cur.x;pos=cur.y;}return {res,pos};
}
struct sgt2{struct node{int mn,pos;}tr[N<<2];void pushup(int u){tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);if(tr[u<<1].mn<=tr[u<<1|1].mn)tr[u].pos=tr[u<<1].pos;else tr[u].pos=tr[u<<1|1].pos;}void build(int u,int l,int r){if(l==r){tr[u].mn=inf;tr[u].pos=l;return;}int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}void modify(int u,int l,int r,int p,int v){if(l==r){tr[u].mn=v;return;}int mid=l+r>>1;if(p<=mid)modify(u<<1,l,mid,p,v);else modify(u<<1|1,mid+1,r,p,v);pushup(u);}pii qry(int u,int l,int r,int L,int R){if(l>=L&&r<=R)return {tr[u].mn,tr[u].pos};int mid=l+r>>1;if(R<=mid)return qry(u<<1,l,mid,L,R);else if(L>mid)return qry(u<<1|1,mid+1,r,L,R);else{auto ql=qry(u<<1,l,mid,L,R);auto qr=qry(u<<1|1,mid+1,r,L,R);int mn=min(ql.x,qr.x);int pos=(ql.x<=qr.x?ql.y:qr.y);return {mn,pos};}}int qry2(int u,int l,int r,int p){if(l==r)return tr[u].mn;int mid=l+r>>1;if(p<=mid)return qry2(u<<1,l,mid,p);else return qry2(u<<1|1,mid+1,r,p);}
}sgt2;
int res;
int lt[N],rt[N];
struct info{int x,v,i;
}a[N];
struct sgt{vector<info>tr[N<<2];struct node1{int a,b,c,t;};struct node2{int u,v,t;};struct nodet{int op,u,v,id,t;};struct noder{int v,t;};stack<node1>s1;stack<node2>s2;stack<nodet>st;stack<noder>sr;void ins(int x,int v,int i,int ti){auto it=qry_path(1,x);if(it.x!=0){s1.push({1,x,-1,ti});modify_path(1,x,-1);st.push({1,x,v,i,ti});s[x].insert({v,i});s2.push({x,sgt2.qry2(1,1,n,dfn[x]),ti});sgt2.modify(1,1,n,dfn[x],s[x].begin()->x);sr.push({v,ti});res+=v;}else{int u=nw[it.y];auto it2=sgt2.qry(1,1,n,dfn[u],dfn[u]+siz[u]-1);int mn=it2.x,pos=nw[it2.y];if(v<mn)return;sr.push({v-mn,ti});res-=mn;res+=v;auto val=*s[pos].begin();st.push({2,pos,val.x,val.y,ti});s[pos].erase(val);s2.push({pos,sgt2.qry2(1,1,n,dfn[pos]),ti});if(!s[pos].empty())sgt2.modify(1,1,n,dfn[pos],s[pos].begin()->x);else sgt2.modify(1,1,n,dfn[pos],inf);s1.push({1,pos,1,ti});modify_path(1,pos,1);st.push({1,x,v,i,ti});s[x].insert({v,i});s2.push({x,sgt2.qry2(1,1,n,dfn[x]),ti});sgt2.modify(1,1,n,dfn[x],s[x].begin()->x);s1.push({1,x,-1,ti});modify_path(1,x,-1);}}void undo(int ti){while(!s1.empty()){auto it=s1.top();if(it.t!=ti)break;s1.pop();modify_path(it.a,it.b,-it.c);}while(!s2.empty()){auto it=s2.top();if(it.t!=ti)break;s2.pop();sgt2.modify(1,1,n,dfn[it.u],it.v);}while(!st.empty()){auto it=st.top();if(it.t!=ti)break;st.pop();if(it.op==1){s[it.u].erase({it.v,it.id});}else{s[it.u].insert({it.v,it.id});}}while(!sr.empty()){auto it=sr.top();if(it.t!=ti)break;sr.pop();res-=it.v;}}void modify(int u,int l,int r,int L,int R,info v){if(l>=L&&r<=R){tr[u].push_back(v);return;}int mid=l+r>>1;if(L<=mid)modify(u<<1,l,mid,L,R,v);if(R>mid)modify(u<<1|1,mid+1,r,L,R,v);}void solve(int u,int l,int r){for(auto it:tr[u]){int x=it.x,v=it.v,i=it.i;ins(x,v,i,u);}int mid=l+r>>1;if(l!=r){solve(u<<1,l,mid);solve(u<<1|1,mid+1,r);}else cout<<res<<' ';undo(u);}
}sgt;
void solve(int cs){if(!cs)return;cin>>Id>>n>>k>>m;for(int i=2;i<=n;i++){int x;cin>>x;add(x,i);}dfs1(1,0);dfs2(1,1);sgt1.build(1,1,n);sgt2.build(1,1,n);for(int i=1;i<=k;i++){int x,v;cin>>x>>v;a[i]={x,v};}for(int i=1;i<=m;i++){int op,x,v,id;cin>>op;if(op==1){cin>>x>>v;a[++k]={x,v};lt[k]=i;}else{cin>>id;rt[id]=i;}}for(int i=1;i<=k;i++){if(!rt[i])rt[i]=m;else rt[i]--;sgt.modify(1,0,m,lt[i],rt[i],{a[i].x,a[i].v,i});}sgt.solve(1,0,m);cout<<'\n';
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// cin>>Tc;// init();for(int cs=1;cs<=Tc;cs++){solve(cs);}// cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';// cerr<<(&st-&ed)/1048576.0<<'\n';return 0;
}