20240724【省选】模拟

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ls now<<1
#define rs now<<1|1
const ll N=2*114514,M=1919810;
struct xx{
	ll next,to;
}e[2*N];
ll head[2*N],cnt;
void add(ll x,ll y){
	e[++cnt].next=head[x];
	e[cnt].to=y;
	head[x]=cnt;
}
ll n,m,fr[N];
ll in[N],out[N],t_cnt;
void dfs(ll u,ll fa){
	in[u]=out[u]=++t_cnt;
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		out[u]=++t_cnt;
	}
}
struct tree{
	ll res,tag;
	ll mx,mn,lmx,rmx;
}t[4*N];
void modify(ll now,ll k){
	t[now].mx+=k,t[now].mn+=k;
	t[now].lmx-=k,t[now].rmx-=k;
	t[now].tag+=k;
}
void pushup(ll now){
	t[now].mx=max(t[ls].mx,t[rs].mx),t[now].mn=min(t[ls].mn,t[rs].mn);
	t[now].lmx=max(max(t[ls].lmx,t[rs].lmx),t[ls].mx-2*t[rs].mn);
	t[now].rmx=max(max(t[ls].rmx,t[rs].rmx),t[rs].mx-2*t[ls].mn);
	t[now].res=max(t[ls].res,t[rs].res);
	t[now].res=max(t[now].res,max(t[ls].mx+t[rs].rmx,t[rs].mx+t[ls].lmx));
}
void pushdown(ll now){
	ll k=t[now].tag;
	if(!k) return;
	modify(ls,k),modify(rs,k);
	t[now].tag=0;
}
void build(ll now,ll l,ll r){
	if(l==r){
		t[now].lmx=t[now].rmx=t[now].res=-1;
		return;
	}
	ll mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(now);
}
void update(ll now,ll l,ll r,ll x,ll y,ll k){
	if(l>=x&&r<=y){
		modify(now,k);
		return;
	}
	pushdown(now);
	ll mid=(l+r)>>1;
	if(x<=mid) update(ls,l,mid,x,y,k);
	if(y>mid) update(rs,mid+1,r,x,y,k);
	pushup(now);
}
ll p,w,a[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=2;i<=n;++i){
		cin>>fr[i];
		add(i,fr[i]),add(fr[i],i);
	}
	build(1,1,n);
	dfs(1,0);
	for(int i=1;i<=m;++i){
		cin>>p>>w;
		update(1,1,t_cnt,in[p],out[p],w-a[p]);
		a[p]=w;
		cout<<t[1].res<<'\n';
	}
	return 0;
}/*5 4
1 1 2 2
4 8
4 3
2 2
5 7
拥有蒟蒻的力量，退役是必然的*/