MnZn自学淀粉树RE了6个点WA#3

using namespace std;
#define ll int
#define MAXN 200010
// By flyfreemrn
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct node_sgt{//动态开点权值线段树 
	ll idx,sum[MAXN*50],son[MAXN*50][2];
	stack <ll> st;
	ll newnode(){
		ll now;
		if(!st.empty())now=st.top(),st.pop();
		else now=++idx;
		sum[now]=son[now][0]=son[now][1]=0;
		return now;
	}
	void insert(ll &now,ll pos,ll val,ll l,ll r){
		if(!now)now=newnode();
		sum[now]+=val;
//		cout<<"insert: "<<now<<" "<<l<<" "<<r<<" "<<sum[now]<<endl;
		if(l==r){
			if(!sum[now]){
				st.push(now);
				now=0;
			}
			return;
		}
		ll mid=(l+r)/2;
		if(pos<=mid)insert(son[now][0],pos,val,l,mid);
		else insert(son[now][1],pos,val,mid+1,r);
		if(!sum[now]){
			st.push(now);
			now=0;
		}
		return;
	}
	ll find(ll now,ll dl,ll dr,ll l,ll r){
		if(!now)return 0;
		if(l>=dl&&r<=dr)return sum[now];
		ll ans=0,mid=(l+r)/2;
		if(dl<=mid)ans+=find(son[now][0],dl,dr,l,mid);
		if(dr>mid)ans+=find(son[now][1],dl,dr,mid+1,r);
		return ans;
	}
}sgt;
bool used[MAXN];
ll n,m,idx;
ll val[MAXN],dep[MAXN];
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
ll p[MAXN][50];
void build(ll x,ll y){
	nxt[++idx]=hd[x];
	ed[idx]=y;
	hd[x]=idx;
}
void dfs1(ll now){//dfs预处理 
	dep[now]=dep[p[now][0]]+1;
	for(int i=1;i<=30;i++)p[now][i]=p[p[now][i-1]][i-1];
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		if(y==p[now][0])continue;
		p[y][0]=now;
		dfs1(y);
	}
}
ll get_len(ll x,ll y){//求树上两点距离 
	ll len=0;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=30;i>=0;i--){
		if(dep[p[x][i]]>=dep[y]){
			x=p[x][i];
			len+=(1<<i);
		}
	}
	if(x==y)return len;
	for(int i=30;i>=0;i--){
		if(p[x][i]!=p[y][i]){
			x=p[x][i],y=p[y][i];
			len+=(1<<i+1);
		}
	}
	return len+2;
}
struct Pt{
	bool used[MAXN];
	ll siz[MAXN],min_siz,min_id;
	void get_siz(ll now,ll fa){//处理子树大小 
		siz[now]=1;
		for(int i=hd[now];i;i=nxt[i]){
			ll y=ed[i];
			if(used[y]||y==fa)continue;
			get_siz(y,now);
			siz[now]+=siz[y];
		}
	}
	void get_rot(ll now,ll fa,ll tot){//查找重心 
		ll mxu=tot-siz[now];
		for(int i=hd[now];i;i=nxt[i]){
			ll y=ed[i];
			if(used[y]||y==p[now][0])continue;
			get_rot(y,now,tot);
			mxu=max(mxu,siz[y]);
		}
		if(mxu<min_siz)min_siz=mxu,min_id=now;
	}
	ll fa[MAXN],id[MAXN],rot[MAXN];
	vector<ll> son[MAXN],rot_son[MAXN];
	void add(ll now,ll _fa,ll &_rot1,ll &_rot2,ll _dep){//递归加点 
//		cout<<now<<" "<<_dep<<" "<<val[now]<<endl;
		sgt.insert(_rot1,_dep,val[now],0,n);
		sgt.insert(_rot2,_dep,val[now],0,n);
		for(int i=hd[now];i;i=nxt[i]){
			ll y=ed[i];
			if(used[y]||y==_fa)continue;
			add(y,now,_rot1,_rot2,_dep+1);
		}
	}
	void solve(ll now){//点分治建树 
		used[now]=true;
		sgt.insert(rot[now],0,val[now],0,n);
		for(int i=hd[now];i;i=nxt[i]){
			ll y=ed[i];
			if(used[y])continue;
			rot_son[now].push_back(0);
			add(y,now,rot[now],rot_son[now][rot_son[now].size()-1],1);
			//处理子树点权 
			get_siz(y,now);
			min_siz=siz[y],min_id=y;
			get_rot(y,now,siz[y]);
			//处理子树y的重心 
			fa[min_id]=now,id[min_id]=son[now].size();
			son[now].push_back(min_id);
			//处理点分树信息 
		}
//		cout<<"solve: "<<now<<" ";
//		for(int i=0;i<son[now].size();i++)cout<<son[now][i]<<" ";
//		cout<<endl;
		for(int i=0;i<son[now].size();i++){//淀粉汁 
			ll y=son[now][i];
			solve(y);
		}
//		used[now]=true;
	}
	void change(ll pos,ll new_val,ll re_val){
		sgt.insert(rot[pos],0,-re_val,0,n);
		sgt.insert(rot[pos],0,new_val,0,n);
		//当前位置更新 
		ll x=fa[pos],_id=id[pos];
		while(x){
			ll _len=get_len(x,pos);
			sgt.insert(rot[x],_len,-re_val,0,n);
			sgt.insert(rot[x],_len,new_val,0,n);
			sgt.insert(rot_son[x][_id],_len,-re_val,0,n);
			sgt.insert(rot_son[x][_id],_len,new_val,0,n);
			_id=id[x],x=fa[x];
			//跳重心更新祖先 
		}
	}
	ll find(ll pos,ll k){
		ll ans=0;
		ans+=sgt.find(rot[pos],0,k,0,n);
//		cout<<pos<<" "<<ans<<endl;
		ll x=fa[pos],_id=id[pos];
		while(x){
			ll _len=get_len(x,pos);
			if(_len>k)break;
			ans+=sgt.find(rot[x],0,min(n,k-_len),0,n);
			ans-=sgt.find(rot_son[x][_id],0,min(n,k-_len),0,n);
			_id=id[x],x=fa[x];
		} 
		return ans;
	}
}Pt;
ll _ans;
int main(){
//	freopen("P6329_1.in","r",stdin);
	n=read(),m=read();
	for(int i=1;i<=n;i++)val[i]=read();
	for(int i=1;i<n;i++){
		ll x=read(),y=read();
		build(x,y);
		build(y,x);
	}
	dfs1(1);
	Pt.get_siz(1,0);
	Pt.min_siz=1e9,Pt.min_id=0;
	Pt.get_rot(1,0,Pt.siz[1]);
	Pt.solve(Pt.min_id);
	for(int i=1;i<=m;i++){
		ll type=read();
		if(type==0){
			ll x=read(),k=read();
			cout<<(_ans=Pt.find(x,k))<<endl;
		}else{
			ll x=read(),y=read();
			Pt.change(x,y,val[x]);
			val[x]=y;
		}
	}
	return 0;
}