这就是线段树解决区间覆盖的一类毒瘤问题
自从xyz111在cf上出了那道线段树解决区间覆盖问题之后，这已经几乎成为了一种毒瘤算法，这道题可以说是有过之而无不及。首先我们考虑一个区间内有正有负，加完之后绝对值的和和三部分有关系1.有负数变成负数，2.由正数变成正数，3.有负数变成正数，前面两种非常好讨论，只有第三种有苦难。但是我们注意到第三种每个数字只会出现一次，所以就变成了区间覆盖的那一类问题，用区间覆盖线段树来解决，复杂度通过势能分析。
所以树链剖分之后随便搞一搞复杂度 $$ O(nlog^2n) $$
//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
int ret=0,f=1; char ch;
for (ch=getchar();ch>'9' || ch<'0';ch=getchar())
if (ch=='-') f=-f;
for (;'0'<=ch && ch<='9';ch=getchar())
ret=ret*10+ch-'0';
return ret*f;
}
const int N = 100010;
int son[N],fa[N],d[N],p[N][20],q[N],w[N],v[N],a[N],top[N],vis[N];
int start[N],to[N<<1],next[N<<1],size[N],cnt;
inline void connect(int a,int b){
to[++cnt]=b; next[cnt]=start[a]; start[a]=cnt;
}
int n,m;
struct node{
int l,r;
int vmax,num;
LL sum,flag;
inline int mid(){ return r+l>>1; }
inline int len(){ return r-l+1; }
inline void add(LL x){
if (vmax!=0 && vmax+x>=0) printf("Wrong!!!\n");
if (vmax!=0) vmax+=x;
flag+=x;
sum+=x*(len()-num-num);
}
}s[N<<2];
void init(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read(); m=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<n;i++){
int x=read(),y=read();
connect(x,y);
connect(y,x);
}
int head=0,tail=1,u;
q[1]=1; d[1]=1; fa[1]=0;
while (head<tail){
u=q[++head];
for (int p=start[u];p;p=next[p]){
int &v=to[p];
if (d[v]) continue;
d[v]=d[u]+1; fa[v]=u;
q[++tail]=v;
}
}
for (int i=n;i;i--){
int x=q[i];
size[x]++;
size[fa[x]]+=size[x];
if (size[son[fa[x]]]<size[x]) son[fa[x]]=x;
}
int now=0;
for (int i=1;i<=n;i++){
int x=q[i];
if (vis[x]) continue;
for (int j=x;j;j=son[j]){
top[j]=x;
w[j]=++now;
vis[j]=1;
v[now]=a[j];
}
}
for (int i=1;i<=n;i++) p[i][0]=fa[i];
for (int j=1;j<20;j++)
for (int i=1;i<=n;i++)
p[i][j]=p[p[i][j-1]][j-1];
}
inline int lca(int x,int y){
if (d[x]<d[y]) swap(x,y);
int j;
while (d[x]>d[y]){
for (j=1;d[p[x][j]]>=d[y];j++);
x=p[x][j-1];
}
while (x!=y){
for (j=1;p[x][j]!=p[y][j];j++);
x=p[x][j-1],y=p[y][j-1];
}
return x;
}
inline void push_down(int x){
if (s[x].r>s[x].l && s[x].flag){
s[x<<1].add(s[x].flag);
s[x<<1|1].add(s[x].flag);
s[x].flag=0;
}
}
inline int gvmax(int x,int y){
if (x>=0) return y;
if (y>=0) return x;
return x>y?x:y;
}
inline void push_up(int x){
s[x].sum=s[x<<1].sum+s[x<<1|1].sum;
s[x].num=s[x<<1].num+s[x<<1|1].num;
s[x].vmax=gvmax(s[x<<1].vmax,s[x<<1|1].vmax);
}
inline void build(int i,int l,int r){
s[i].l=l; s[i].r=r;
s[i].flag=0;
if (l==r){
s[i].num=v[l]<0?1:0;
s[i].vmax=min(0,v[l]);
s[i].sum=abs(v[l]);
return;
}
int m=l+r>>1;
build(i<<1,l,m); build(i<<1|1,m+1,r);
push_up(i);
}
inline LL query(int i,int l,int r){
if (s[i].l==l && s[i].r==r){
return s[i].sum;
}
push_down(i);
int m=s[i].mid();
LL ret;
if (r<=m) ret=query(i<<1,l,r);
else if (l>m) ret=query(i<<1|1,l,r);
else ret=query(i<<1,l,m)+query(i<<1|1,m+1,r);
push_up(i);
return ret;
}
inline void dfs(int i,int d){
if (s[i].vmax==0 || s[i].vmax+d<0){
s[i].add(d);
return;
}
if (s[i].l==s[i].r){
s[i].sum=s[i].vmax+d;
s[i].vmax=0;
s[i].num=0;
return;
}
push_down(i);
dfs(i<<1,d);
dfs(i<<1|1,d);
push_up(i);
}
inline void modify(int i,int l,int r,int d){
if (s[i].l==l && s[i].r==r){
dfs(i,d);
return;
}
push_down(i);
int m=s[i].mid();
if (r<=m) modify(i<<1,l,r,d);
else if (l>m) modify(i<<1|1,l,r,d);
else modify(i<<1,l,m,d),modify(i<<1|1,m+1,r,d);
push_up(i);
}
inline LL Query(int x,int y){
LL ans=0;
int u=lca(x,y);
while (d[x]>d[u]){
if (d[top[x]]>d[u]){
ans+=query(1,w[top[x]],w[x]);
x=fa[top[x]];
}else{
ans+=query(1,w[son[u]],w[x]);
x=u;
}
}
swap(x,y);
while (d[x]>d[u]){
if (d[top[x]]>d[u]){
ans+=query(1,w[top[x]],w[x]);
x=fa[top[x]];
}else{
ans+=query(1,w[son[u]],w[x]);
x=u;
}
}
ans+=query(1,w[u],w[u]);
return ans;
}
inline void Modify(int x,int y,int D){
int u=lca(x,y);
while (d[x]>d[u]){
if (d[top[x]]>d[u]){
modify(1,w[top[x]],w[x],D);
x=fa[top[x]];
}else{
modify(1,w[son[u]],w[x],D);
x=u;
}
}
swap(x,y);
while (d[x]>d[u]){
if (d[top[x]]>d[u]){
modify(1,w[top[x]],w[x],D);
x=fa[top[x]];
}else{
modify(1,w[son[u]],w[x],D);
x=u;
}
}
modify(1,w[u],w[u],D);
return;
}
void work()
{
build(1,1,n);
for (int i=1;i<=m;i++){
int op=read(),x=read(),y=read();
if (op==2){
printf("%lld\n",Query(x,y));
}else{
int d=read();
Modify(x,y,d);
}
}
}
int main()
{
init();
work();
return 0;
}
