蒟蒻求助QAQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100100
#define int long long
int n,m,tot,cnt;
int head[N],num[N],dep[N],fa[N],dfn[N],rk[N],tp[N],siz[N],son[N];
struct Edge{
	int nxt,to;
}edge[N*2];
struct Tree{
	int l,r,sum,lz,lm,rm,maxn;
	bool f;
	Tree(){l=r=sum=lz=lm=rm=maxn=f=0;}
}tree[N*4];
void add(int from,int to)
{
	edge[++cnt].nxt=head[from];
	edge[cnt].to=to;
	head[from]=cnt;
}
void dfs1(int cur,int pre)
{
	dep[cur]=dep[pre]+1;
	fa[cur]=pre;
	siz[cur]=1;
	for(int i=head[cur];i;i=edge[i].nxt)
	{
		int nxt=edge[i].to;
		if(nxt==pre)continue;
		dfs1(nxt,cur);
		siz[cur]+=siz[nxt];
		if(siz[son[cur]]<siz[nxt])son[cur]=nxt;
	}
}
void dfs2(int cur,int top)
{
	dfn[cur]=++tot;
	rk[tot]=cur;
	tp[cur]=top;
	if(son[cur])dfs2(son[cur],top);
	for(int i=head[cur];i;i=edge[i].nxt)
	{
		int nxt=edge[i].to;
		if(nxt==fa[cur]||nxt==son[cur])continue;
		dfs2(nxt,nxt);
	}
}
Tree merge(Tree x,Tree y)
{
	Tree c;
	c.maxn=max(max(x.maxn,y.maxn),x.rm+y.lm);
	c.maxn=max(c.maxn,0ll);
	c.lm=max(x.lm,x.sum+y.lm);
	c.lm=max(c.lm,0ll);
	c.rm=max(y.rm,y.sum+x.rm);
	c.rm=max(c.rm,0ll);
	c.sum=x.sum+y.sum;
	return c;
}
void pushup(int id)
{
	tree[id].maxn=max(tree[id*2].rm+tree[id*2+1].lm,max(tree[id*2].maxn,tree[id*2+1].maxn));
	tree[id].maxn=max(tree[id].maxn,0ll);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
	tree[id].lm=max(tree[id*2].lm,tree[id*2].sum+tree[id*2+1].lm);
	tree[id].lm=max(tree[id].lm,0ll);
	tree[id].rm=max(tree[id*2+1].rm,tree[id*2+1].sum+tree[id*2].rm);
	tree[id].rm=max(tree[id].rm,0ll);
}
void pushdown(int id)
{
	if(!tree[id].f)return;
	int mid=(tree[id].l+tree[id].r)/2;
	tree[id*2].f=tree[id*2+1].f=1;
	tree[id*2].lz=tree[id*2+1].lz=tree[id].lz;
	tree[id*2].sum=(mid-tree[id].l+1)*tree[id].lz;
	tree[id*2].maxn=tree[id*2].lm=tree[id*2].rm=max(tree[id*2].sum,0ll);
	tree[id*2+1].sum=(tree[id].r-mid)*tree[id].lz;
	tree[id*2+1].maxn=tree[id*2+1].lm=tree[id*2+1].rm=max(tree[id*2+1].sum,0ll);
	tree[id].f=tree[id].lz=0;
}
void build(int id,int l,int r)
{
	tree[id].l=l;tree[id].r=r;
	if(l==r)
	{
		tree[id].sum=num[rk[l]];
		tree[id].lm=tree[id].rm=tree[id].maxn=max(num[l],0ll);
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	pushup(id);
}
void make(int id,int l,int r,int k)
{
	if(l<=tree[id].l&&tree[id].r<=r)
	{
		tree[id].f=1;
		tree[id].lz=k;
		tree[id].sum=(tree[id].r-tree[id].l+1)*k;
		tree[id].maxn=tree[id].lm=tree[id].rm=max(tree[id].sum,0ll);
		return;
	}
	pushdown(id);
	int mid=(tree[id].l+tree[id].r)/2;
	if(l<=mid)make(id*2,l,r,k);
	if(r>mid)make(id*2+1,l,r,k);
	pushup(id);
}
Tree find(int id,int l,int r)
{
	if(l<=tree[id].l&&tree[id].r<=r)return tree[id];
	pushdown(id);
	int mid=(tree[id].l+tree[id].r)/2;
	if(r<=mid)return find(id*2,l,r);
	else if(l>mid)return find(id*2+1,l,r);
	else
	{
		Tree x=find(id*2,l,r),y=find(id*2+1,l,r),c;
		c.maxn=max(max(x.maxn,y.maxn),x.rm+y.lm);
		c.maxn=max(c.maxn,0ll);
		c.lm=max(x.lm,x.sum+y.lm);
		c.lm=max(c.lm,0ll);
		c.rm=max(y.rm,y.sum+x.rm);
		c.rm=max(c.rm,0ll);
		c.sum=x.sum+y.sum;
		return c;
	}
}
void makef(int x,int y,int k)
{
	while(tp[x]!=tp[y])
	{
		if(dep[tp[x]]<dep[tp[y]])swap(x,y);
		make(1,dfn[tp[x]],dfn[x],k);
		x=fa[tp[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	make(1,dfn[y],dfn[x],k);
}
Tree findf(int x,int y)
{
	Tree ans;
	while(tp[x]!=tp[y])
	{
		if(dep[tp[x]]<dep[tp[y]])swap(x,y);
		ans=merge(ans,find(1,dfn[tp[x]],dfn[x]));
		x=fa[tp[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	ans=merge(ans,find(1,dfn[y],dfn[x]));
	return ans;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)scanf("%lld",&num[i]);
	for(int i=1;i<n;++i)
	{
		int a,b;
		scanf("%lld%lld",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	scanf("%lld",&m);
	for(int i=1;i<=m;++i)
	{
		int k,x,y,z;
		scanf("%lld",&k);
		if(k==1)
		{
			scanf("%lld%lld",&x,&y);
			Tree tmp=findf(x,y);
			printf("%lld\n",max(max(tmp.lm,tmp.rm),max(tmp.maxn,0ll)));
		}
		else if(k==2)
		{
			scanf("%lld%lld%lld",&x,&y,&z);
			makef(x,y,z);
		}
	}
	return 0;
}