接下来一行n个整数a_i,表示点i的权值

接下来n-1行,每行两个整数u,v表示存在一条(u,v)的边

接下来m行,每行一个操作,输入格式见题目描述

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

typedef long long ll;

const int BufferSize=1<<16;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

	if(head==tail) {

		int l=fread(buffer,1,BufferSize,stdin);

		tail=(head=buffer)+l;

	}

	return *head++;

}

inline int read() {

    int x=0,f=1;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';

    return x*f;

}

const int maxn=100010;

const ll inf=1ll<<60;

int n,m,val[maxn],first[maxn],next[maxn<<1],to[maxn<<1],e;

void AddEdge(int u,int v) {

	to[++e]=v;next[e]=first[u];first[u]=e;

	to[++e]=u;next[e]=first[v];first[v]=e;

}

int dep[maxn],fa[maxn],siz[maxn],son[maxn];

void dfs(int x) {

	dep[x]=dep[fa[x]]+1;siz[x]=1;

	ren if(to[i]!=fa[x]) {

		fa[to[i]]=x;dfs(to[i]);

		siz[x]+=siz[to[i]];

		if(siz[to[i]]>siz[son[x]]) son[x]=to[i];

	}

}

int top[maxn],st[maxn],pos[maxn],ToT;

void build(int x,int tp) {

	top[x]=tp;st[x]=++ToT;pos[ToT]=x;

	if(son[x]) build(son[x],tp);

	ren if(to[i]!=fa[x]&&to[i]!=son[x]) build(to[i],to[i]);

}

ll sumv[maxn<<2],addv[maxn<<2],maxv[maxn<<2],ctot[maxn<<2];

void maintain(int o,int l,int r) {

	int lc=o<<1,rc=lc|1;

	sumv[o]=sumv[lc]+sumv[rc];

	maxv[o]=max(-inf,max(maxv[lc],maxv[rc]));

	ctot[o]=ctot[lc]+ctot[rc];

	if(addv[o]) sumv[o]+=ctot[o]*addv[o],maxv[o]+=addv[o];

}

void pushdown(int o) {

	if(addv[o]) {

		int lc=o<<1,rc=lc|1;

		addv[lc]+=addv[o];addv[rc]+=addv[o];

		sumv[lc]+=addv[o]*ctot[lc];sumv[rc]+=addv[o]*ctot[rc];

		maxv[lc]+=addv[o];maxv[rc]+=addv[o];

		addv[o]=0;

	}

}

void build(int o,int l,int r) {

	if(l==r) {

		sumv[o]=abs(val[pos[l]]);

		maxv[o]=val[pos[l]]<0?val[pos[l]]:-inf;

		ctot[o]=val[pos[l]]>=0?1:-1;

	}

	else {

		int mid=l+r>>1,lc=o<<1,rc=lc|1;

		build(lc,l,mid);build(rc,mid+1,r);

		maintain(o,l,r);

	}

}

ll query(int o,int l,int r,int ql,int qr) {

	if(ql<=l&&r<=qr) return sumv[o];

	else {

		pushdown(o);ll res=0;

		int mid=l+r>>1,lc=o<<1,rc=lc|1;

		if(ql<=mid) res+=query(lc,l,mid,ql,qr);

		if(qr>mid) res+=query(rc,mid+1,r,ql,qr);

		return res;

	}

}

void update(int o,int l,int r,int ql,int qr,int v) {

	if(ql<=l&&r<=qr) {

		if(maxv[o]+v>=0) {

			if(l==r) {

				addv[o]=0;sumv[o]=v-sumv[o];

				maxv[o]=-inf;ctot[o]=1;

			}

			else {

				pushdown(o);int mid=l+r>>1,lc=o<<1,rc=lc|1;

				update(lc,l,mid,ql,qr,v);update(rc,mid+1,r,ql,qr,v);

				maintain(o,l,r);

			}

		}

		else {

			if(l<r) addv[o]+=v,maintain(o,l,r);

			else sumv[o]+=ctot[o]*v,maxv[o]+=v;

		}

	}

	else {

		pushdown(o);int mid=l+r>>1,lc=o<<1,rc=lc|1;

		if(ql<=mid) update(lc,l,mid,ql,qr,v);

		if(qr>mid) update(rc,mid+1,r,ql,qr,v);

		maintain(o,l,r);

	}

}

void query(int x,int y) {

	int f1=top[x],f2=top[y];ll ans=0;

	while(f1!=f2) {

		if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);

		ans+=query(1,1,n,st[f1],st[x]);

		x=fa[f1];f1=top[x];

	}

	if(dep[x]>dep[y]) swap(x,y);

	printf("%lld\n",ans+query(1,1,n,st[x],st[y]));

}

void update(int x,int y,int v) {

	int f1=top[x],f2=top[y];

	while(f1!=f2) {

		if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);

		update(1,1,n,st[f1],st[x],v);

		x=fa[f1];f1=top[x];

	}

	if(dep[x]>dep[y]) swap(x,y);

	update(1,1,n,st[x],st[y],v);

}

int main() {

	n=read();m=read();

	rep(i,1,n) val[i]=read();

	rep(i,2,n) AddEdge(read(),read());

	dfs(1);build(1,1);

	build(1,1,n);

	while(m--) {

		int t=read(),x=read(),y=read();

		if(t==1) update(x,y,read());

		else query(x,y);

	}

	return 0;

}