如题

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+5;
#define int long long

int n,q;
vector<int> g[N];
int a[N];
int dep[N],f[N],siz[N],wc[N],dfn[N],tottime,top[N],val[N],rdfn[N];
void dfs1(int u,int fa){
	f[u]=fa,siz[u]=1,dep[u]=dep[fa]+1;
	for(auto v:g[u]){
		if(v==fa) continue;
		dfs1(v,u),siz[u]+=siz[v];
		if(siz[v]>siz[wc[u]]) wc[u]=v;
	}
}
void dfs2(int u,int TOP){
	top[u]=TOP,dfn[u]=++tottime,rdfn[tottime]=u;
	if(wc[u]) dfs2(wc[u],TOP);
	for(auto v:g[u]){
		if(v==f[u]||v==wc[u]) continue;
		dfs2(v,v);
	}
}
int laz[N<<2];
struct node{int l,r,ans,sum;void init(){l=r=ans=sum=0;}}d[N<<2];
node merge(node l,node r){
	node re;re.init();
	re.l=max(l.l,l.sum+r.l),re.r=max(r.r,r.sum+l.r);
	re.sum=l.sum+r.sum;
	re.ans=max({l.ans,r.ans,l.r+r.l});
	return re;
}
void build(int s,int t,int p){
	laz[p]=-114514;
	if(s==t){
		d[p].sum=a[rdfn[s]];
		d[p].ans=d[p].l=d[p].r=max(d[p].sum,0ll);
		return ;
	}
	int mid=(s+t)>>1;
	build(s,mid,p*2);build(mid+1,t,p*2+1);
	d[p]=merge(d[p*2],d[p*2+1]);
}
void pushup(int s,int t,int p){
	int mid=(s+t)>>1;
	if(laz[p]!=-114514){
		d[p*2].sum=laz[p]*(mid-s+1);
		d[p*2].l=d[p*2].r=d[p*2].ans=max(0ll,d[p*2].sum);
		d[p*2+1].sum=laz[p]*(t-mid);
		d[p*2+1].l=d[p*2+1].r=d[p*2+1].ans=max(0ll,d[p*2+1].sum);
		laz[p*2]=laz[p],laz[p*2+1]=laz[p];
		laz[p]=-114514;
	}
}
void update(int l,int r,int s,int t,int p,int c){
	if(l<=s&&t<=r){
		d[p].sum=c*(t-s+1);
		d[p].l=d[p].r=d[p].ans=max(0ll,d[p].sum);
		laz[p]=c;
		return ;
	}
	int mid=(s+t)>>1;
	pushup(s,t,p);
	if(l<=mid) update(l,r,s,mid,p*2,c);
	if(r>mid) update(l,r,mid+1,t,p*2+1,c);
	d[p]=merge(d[p*2],d[p*2+1]);
}
node get_ans(int l,int r,int s,int t,int p){
	if(l<=s&&t<=r) return d[p];
	int mid=(s+t)>>1;
	pushup(s,t,p);
	if(r<=mid) return get_ans(l,r,s,mid,p*2);
	if(l>mid) return get_ans(l,r,mid+1,t,p*2+1);
	return merge(get_ans(l,r,s,mid,p*2),get_ans(l,r,mid+1,t,p*2+1));
}
void Update(int x,int y,int c){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update(dfn[top[x]],dfn[x],1,n,1,c);
		x=f[top[x]];
	}
	update(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),1,n,1,c);
}
node Get_Ans(int x,int y){
	node l,r;l.init(),r.init();
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			r=merge(get_ans(dfn[top[y]],dfn[y],1,n,1),r),y=f[top[y]];
		else
			l=merge(l,get_ans(dfn[top[x]],dfn[x],1,n,1)),x=f[top[x]];
	}
	if(dep[x]<dep[y]) r=merge(get_ans(dfn[x],dfn[y],1,n,1),r);
	else l=merge(l,get_ans(dfn[y],dfn[x],1,n,1));
	return merge(l,r);
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		g[u].push_back(v);g[v].push_back(u);
	}
	dfs1(1,1),dfs2(1,1),build(1,n,1);
	cin>>q;
	while(q--){
		int opt,a,b,c;
		cin>>opt>>a>>b;
		if(opt==1){
			cout<<max(Get_Ans(a,b).ans,0ll)<<'\n';
		}
		else{
			cin>>c;
			Update(a,b,c);
		}
		//cout<<get_ans(7,8,1,n,1).sum<<':'<<get_ans(9,9,1,n,1).sum<<':'<<get_ans(7,9,1,n,1).sum<<':'<<'\n';
	}
	return 0;
}