求助树剖，WA on test#11

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[1000005];
int cnt,head[1000005];
int tot,fa[100005],rnk[100005],dfn[100005],son[100005],siz[100005],top[100005],dep[100005];
struct data{
	int sum,maxf,lmax,rmax,tag=-10211314;
}t[1000005];
struct edge{
	int to,nxt;
}e[200005];
void addedge(int u,int v){
	e[++cnt]={v,head[u]};
	head[u]=cnt;
}
data newa(){
	data tmp;
	tmp.maxf=tmp.lmax=tmp.rmax=tmp.sum=0;
	tmp.tag=-10211314;
	return tmp;
}
void dfs1(int u){
	siz[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		if(!dep[e[i].to]){
			dep[e[i].to]=dep[u]+1;
			fa[e[i].to]=u;
			dfs1(e[i].to);
			siz[u]+=siz[e[i].to];
			if(siz[e[i].to]>siz[son[u]])son[u]=e[i].to;
		}
	}
}
void dfs2(int u,int f){
	top[u]=f,dfn[u]=++tot,rnk[tot]=u;
	if(son[u])dfs2(son[u],f);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v!=fa[u]&&v!=son[u])dfs2(e[i].to,e[i].to);
	}
}
data pushup(data ls,data rs){
	data res;
	res.sum=ls.sum+rs.sum;
	res.lmax=max(ls.lmax,ls.sum+rs.lmax);
	res.rmax=max(rs.rmax,rs.sum+ls.rmax);
	res.maxf=max({ls.maxf,rs.maxf,ls.rmax+rs.lmax});
	return res;
}
void pushdown(int o,int l,int r){
	if(t[o].tag==-10211314)return ;
	t[o<<1].tag=t[o<<1|1].tag=t[o].tag;
	int p=t[o].tag;
	int mid=l+r>>1;
	t[o<<1].sum=p*(mid-l+1);
	t[o<<1|1].sum=p*(r-mid);
	t[o<<1|1].rmax=t[o<<1|1].lmax=t[o<<1|1].maxf=max(0ll,p*(r-mid));
	t[o<<1].rmax=t[o<<1].lmax=t[o<<1].maxf=max(0ll,p*(mid-l+1));
	t[o].tag=-10211314;
}
void build(int o,int l,int r){
	if(l==r){
		t[o].sum=a[rnk[r]];
		t[o].maxf=t[o].rmax=t[o].lmax=max(a[rnk[o]],0ll);
		return ;
	}
	int mid=l+r>>1;
	build(o<<1,l,mid);
	build(o<<1|1,mid+1,r);
	t[o]=pushup(t[o<<1],t[o<<1|1]);
}
void update(int o,int l,int r,int x,int y,int p){
	if(l>=x&&r<=y){
		t[o].tag=p;
		t[o].sum=p*(r-l+1);
		t[o].rmax=t[o].lmax=t[o].maxf=max(0ll,p*(r-l+1));
		return ;
	}
	pushdown(o,l,r);
	int mid=l+r>>1;
	if(x<=mid)update(o<<1,l,mid,x,y,p);
	if(y>mid)update(o<<1|1,mid+1,r,x,y,p);
	t[o]=pushup(t[o<<1],t[o<<1|1]);
}
data query(int o,int l,int r,int x,int y){
//	cout<<o<<' '<<t[o].maxf<<endl;
	if(l>=x&&r<=y){
		return t[o];
	}
	pushdown(o,l,r);
	int mid=l+r>>1;
	if(x<=mid&&y>mid)return pushup(query(o<<1,l,mid,x,y),query(o<<1|1,mid+1,r,x,y));
	if(x<=mid)return query(o<<1,l,mid,x,y);
	if(y>mid)return query(o<<1|1,mid+1,r,x,y);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	dep[1]=1;
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	cin>>q;
	while(q--){
		int op,u,v;
		cin>>op>>u>>v;
		if(op==1){
			data ans=newa(),res1=newa(),res2=newa();
			while(top[u]!=top[v]){
				if(dep[top[u]]<dep[top[v]]){
					res2=pushup(query(1,1,n,dfn[top[v]],dfn[v]),res2);
					v=fa[top[v]];
				}
				else {
					res1=pushup(query(1,1,n,dfn[top[u]],dfn[u]),res1);
					u=fa[top[u]];
				}
//				cout<<ans.maxf<<endl;
			}
			if(dep[u]>dep[v]){
				res1=pushup(query(1,1,n,dfn[v],dfn[u]),res1);
			}
			else res2=pushup(query(1,1,n,dfn[u],dfn[v]),res2);
			swap(res1.lmax,res1.rmax);
			ans=pushup(res1,res2);
			cout<<ans.maxf<<endl;
		}
		else {
			int p;
			cin>>p;
			while(top[u]!=top[v]){
				if(dep[top[u]]<dep[top[v]])swap(u,v);
				update(1,1,n,dfn[top[u]],dfn[u],p);
				u=fa[top[u]];
			}
			if(dep[u]>dep[v])swap(u,v);
			update(1,1,n,dfn[u],dfn[v],p);
		}
	}
}