一道题目，大意是一颗带点权的树，每次可以选择一个最小点权 $\gt 0$ 的联通块给每个点减一，问最少几次能把所有点变成 $0$。多次询问，每次询问前单点修改点权。修改操作永久留存，减少操作对于修改操作独立。

结论是 $\sum_{i=1}^{n}\max{\{a_i-a_{{father}_i},0\}}$，这里使用 FHQ-Treap 维护，在如下样例出现问题：

10 5
39 24 1 16 13 31 90 69 7 34
1 2
1 3
1 4
4 5
4 6
6 7
1 8
6 9
6 10
2 96
4 95
8 40
9 26
6 97

其中，正确输出为：

203
244
215
215
155

发现代码输出与随机种子有关，而这本来是不应该出现的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,u,v,x,y;
const int maxn=1e6+5;
vector<int> G[maxn];
int a[maxn];
int ans;
int fa[maxn];

mt19937 rng(13533);
struct node{
	int ls,rs,val,sz,sum;
	unsigned int prio;
}fhq[maxn*2];
int cnt,rt[maxn];
int newnode(int val){
	fhq[++cnt]=node{0,0,val,1,val,rng()};
	return cnt;
}
void pushup(int p){
	fhq[p].sz=fhq[fhq[p].ls].sz+fhq[fhq[p].rs].sz+1;
	fhq[p].sum=fhq[fhq[p].ls].sum+fhq[fhq[p].rs].sum+fhq[p].val;
}
void split(int p,int k,int &x,int &y){
	if(!p) return (void)(x=y=0);
	if(fhq[p].val<=k){
		x=p;
		split(fhq[p].rs,k,fhq[p].rs,y);
	}else{
		y=p;
		split(fhq[p].ls,k,x,fhq[p].ls);
	}
	pushup(p);
}
int merge(int x,int y){
	if(!x||!y) return x|y;
	if(fhq[x].prio<fhq[y].prio){
		fhq[x].rs=merge(fhq[x].rs,y);
		pushup(x);
		return x;
	}else{
		fhq[y].ls=merge(x,fhq[y].ls);
		pushup(y);
		return y;
	}
}
void dfs(int u,int f){
	fa[u]=f;
	ans+=max(a[u]-a[f],0ll);
	rt[f]=merge(rt[f],newnode(a[u]));
	for(int v:G[u]){
		if(v==f) continue;
		dfs(v,u);
	}
}
void ins(int &p,int val){
	int x,y;
	split(p,val,x,y);
	p=merge(x,merge(newnode(val),y));
}
void del(int &p,int val){
	int x,y,z;
	split(p,val,y,z);
	split(y,val-1,x,y);
	y=merge(fhq[y].ls,fhq[y].rs);
	p=merge(x,merge(y,z));
}
int calc(int &p,int val){
	int x,y;
	split(p,val,x,y);
	int res=fhq[y].sum-fhq[y].sz*val;
	p=merge(x,y);
	return res;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i) scanf("%lld",a+i);
	for(int i=1;i<n;++i) scanf("%lld%lld",&u,&v),G[u].emplace_back(v),G[v].emplace_back(u);
	dfs(1,0);
	while(m--){
		scanf("%lld%lld",&x,&y);
		ans-=max(a[x]-a[fa[x]],0ll);
		ans-=calc(rt[x],a[x]);
		del(rt[fa[x]],a[x]);
		a[x]=y;
		ans+=max(a[x]-a[fa[x]],0ll);
		ans+=calc(rt[x],a[x]);
		ins(rt[fa[x]],a[x]);
		printf("%lld\n",ans);
	}
}