【题目描述】：
    给定一棵树,设计数据结构支持以下操作
    1 u v d 表示将路径(u,v)加d
    2 u v 表示询问路径(u,v)上点权绝对值的和
【题目解法】：
    看似很不可做，因为有些树的符号在求和时要改变
    然而我们观察一下数据范围：对于100%的数据，n,m <= 10^5 且 0<= d,|a_i|<= 10^8
    为什么d没有绝对值符号呢？这样我们可以发现一条重要的结论：所有数最多只会从负数变成正数一次
    也就是说加入在某次+d后某个数由负数变成了正数，那么我们就暴力修改即可
    由于这样的暴力只会有n次，所以复杂度就是O(n log n)，显然是用线段树实现
    然后只要维护区间最大负数值判断即可
【未完待续？】：
    如果d可以为负数怎么破？
【调整栈空间】：
    编译时加上  -Wl,--stack,10000000

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100005;
const long long INF=(long long)3208320832083208;
struct node {long long maxt,sum1,sum2,lazy,num1,num2;} tree[N*4];
struct edge {int x,next;} b[N*2];
int n,m,tot,a[N],c[N],dfn[N]; long long ans,delta;
int dep[N],top[N],id[N],fa[N],son[N],size[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline void addedge(int x,int y)
{
    ++tot; b[tot].x=y; b[tot].next=a[x]; a[x]=tot;
}
void init()
{
    n=getint(); m=getint();
    for (int i=1; i<=n; i++) c[i]=getint();
    for (int i=1; i<=n-1; i++) 
    {
        int x=getint(),y=getint(); 
        addedge(x,y); addedge(y,x);
    }
}
void dfs1(int x,int pre,int depth)
{
    fa[x]=pre; dep[x]=depth; size[x]=1; int k=0;
    for (int p=a[x];p;p=b[p].next)
    {
        int pp=b[p].x; if (pp==pre) continue;
        dfs1(pp,x,depth+1); size[x]+=size[pp];
        if (size[pp]>k) k=size[pp],son[x]=pp;
    }
}
void dfs2(int x,int ancestor)
{
    top[x]=ancestor; ++tot; id[x]=tot; dfn[tot]=x;
    if (son[x]!=0) dfs2(son[x],ancestor);
    for (int p=a[x];p;p=b[p].next)
    {
        int pp=b[p].x; if (pp==fa[x]) continue;
        if (pp==son[x]) continue; dfs2(pp,pp);
    }
}
void LCT()
{
    tot=0; dfs1(1,0,1); dfs2(1,1);
}
inline void lazy_tag(int p)
{
    if (tree[p].lazy==0) return;  int lc=p*2,rc=p*2+1;
    tree[lc].lazy+=tree[p].lazy;
    tree[rc].lazy+=tree[p].lazy;
    tree[lc].maxt+=tree[p].lazy;
    tree[rc].maxt+=tree[p].lazy;
    tree[lc].sum1+=(long long)tree[lc].num1*tree[p].lazy;
    tree[rc].sum1+=(long long)tree[rc].num1*tree[p].lazy;
    tree[lc].sum2+=(long long)tree[lc].num2*tree[p].lazy;
    tree[rc].sum2+=(long long)tree[rc].num2*tree[p].lazy;
    tree[p].lazy=0;
}
void build(int p,int l,int r)
{
    if (l==r)
    {
        int now=c[dfn[l]];
        if (now>=0) tree[p].maxt=-INF; else tree[p].maxt=now;
        if (now>=0) tree[p].sum1=now; else tree[p].sum2=now;
        if (now>=0) tree[p].num1=1; else tree[p].num2=1;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid); build(p*2+1,mid+1,r);
    tree[p].maxt=max(tree[p*2].maxt,tree[p*2+1].maxt);
    tree[p].sum1=tree[p*2].sum1+tree[p*2+1].sum1;
    tree[p].sum2=tree[p*2].sum2+tree[p*2+1].sum2;
    tree[p].num1=tree[p*2].num1+tree[p*2+1].num1;
    tree[p].num2=tree[p*2].num2+tree[p*2+1].num2;
}
void modify(int p,int l,int r)
{
    if (l!=r) lazy_tag(p); int mid=(l+r)/2;
    if (!((tree[p].maxt<0)&&(tree[p].maxt+delta>=0)))
    {
        tree[p].lazy+=delta; tree[p].maxt+=delta;
        tree[p].sum1+=tree[p].num1*delta;
        tree[p].sum2+=tree[p].num2*delta;
        return;
    }
    if (l==r)
    {
        tree[p].maxt=-INF; tree[p].sum1=tree[p].sum2+delta;
        tree[p].sum2=0; tree[p].num1=1; tree[p].num2=0;
        return;
    }
    modify(p*2,l,mid); modify(p*2+1,mid+1,r);
    tree[p].maxt=max(tree[p*2].maxt,tree[p*2+1].maxt);
    tree[p].sum1=tree[p*2].sum1+tree[p*2+1].sum1;
    tree[p].sum2=tree[p*2].sum2+tree[p*2+1].sum2;
    tree[p].num1=tree[p*2].num1+tree[p*2+1].num1;
    tree[p].num2=tree[p*2].num2+tree[p*2+1].num2;
}
void getseg(int p,int l,int r,int ll,int rr)
{
    if (l!=r) lazy_tag(p); int mid=(l+r)/2;
    if ((l==ll)&&(r==rr)) {modify(p,l,r); return;}
    if (rr<=mid) getseg(p*2,l,mid,ll,rr);
    else if (ll>mid) getseg(p*2+1,mid+1,r,ll,rr);
    else getseg(p*2,l,mid,ll,mid),getseg(p*2+1,mid+1,r,mid+1,rr);
    tree[p].maxt=max(tree[p*2].maxt,tree[p*2+1].maxt);
    tree[p].sum1=tree[p*2].sum1+tree[p*2+1].sum1;
    tree[p].sum2=tree[p*2].sum2+tree[p*2+1].sum2;
    tree[p].num1=tree[p*2].num1+tree[p*2+1].num1;
    tree[p].num2=tree[p*2].num2+tree[p*2+1].num2;
}
long long ask(int p,int l,int r,int ll,int rr)
{
    if (l!=r) lazy_tag(p); int mid=(l+r)/2;
    if ((l==ll)&&(r==rr)) return tree[p].sum1-tree[p].sum2;
    if (rr<=mid) return ask(p*2,l,mid,ll,rr);
    else if (ll>mid) return ask(p*2+1,mid+1,r,ll,rr);
    else return ask(p*2,l,mid,ll,mid)+ask(p*2+1,mid+1,r,mid+1,rr);
}
void modify(int l,int r)
{
    while (top[l]!=top[r])
    {
        if (dep[top[l]]<dep[top[r]]) swap(l,r);
        getseg(1,1,n,id[top[l]],id[l]); l=fa[top[l]];
    }
    if (dep[l]>dep[r]) swap(l,r);
    getseg(1,1,n,id[l],id[r]);
}
void ask(int l,int r)
{
    ans=0;
    while (top[l]!=top[r])
    {
        if (dep[top[l]]<dep[top[r]]) swap(l,r);
        ans+=ask(1,1,n,id[top[l]],id[l]); l=fa[top[l]];
    }
    if (dep[l]>dep[r]) swap(l,r);
    ans+=ask(1,1,n,id[l],id[r]); printf("%I64d\n",ans);
}
void solve()
{
    for (int i=1; i<=m; i++)
    {
        int opt=getint();
        if (opt==1) {int x=getint(),y=getint(); delta=getint(); modify(x,y);}
        if (opt==2) {int x=getint(),y=getint(); ask(x,y);}
    }
}
int main()
{
    init();
    LCT();
    build(1,1,n);
    solve();
    return 0;
}
//!!I64d->lld