大致题意： 给定一棵树，两种操作：给一条树上路径权值加上(x)；求一条树上路径权值绝对值之和。
前言
我又瞎了，原来权值加上的(x)是非负的啊。。。
树剖
首先，显然我们可以通过树剖把树上路径转变为序列上一段区间。
这样一来，就可以用线段树维护了。
线段树
考虑我们记录下每个区间内最大的负数，如果某一时刻这个负数被加成了正数，就暴力修改它更新信息。
由于每个数最多变为正数一次，所以复杂度就有了保证。
不过除此之外，为了方便区间信息维护，还要记录非负数和负数个数之差，以维护绝对值之和。具体实现详见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LL long long
#define RL Reg LL
#define CL Con LL&
#define INF 1e18
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
int n,a[N+5],ee,lnk[N+5];struct edge {int to,nxt;}e[N<<1];
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define pc(c) (C==E&&(clear(),0),*C++=c)
#define tn (x<<3)+(x<<1)
#define D isdigit(c=tc())
int f,T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
public:
I FastIO() {A=B=FI,C=FO,E=FO+FS;}
Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x) {x<0&&cerr<<"ERROR"<<endl;W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);pc('
');}
I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
#undef D
}F;
class TreeChainDissection
{
private:
int d,v[N+5],D[N+5],p[N+5],sz[N+5],f[N+5],s[N+5],tp[N+5];
class SegmentTree
{
private:
#define PT CI l=1,CI r=n,CI rt=1
#define LT l,mid,rt<<1
#define RT mid+1,r,rt<<1|1
#define PU(x) (O[x]=O[x<<1]+O[x<<1|1])
#define PD(x) O[x].F&&(F5(x<<1,l,mid,O[x].F),F5(x<<1|1,mid+1,r,O[x].F),O[x].F=0)
#define F5(x,l,r,v) (O[x].U(v)&&(BF(O[x].P,v,l,r,x),0))
struct node
{
int P,T;LL Mx,F,S;
I node(CI p=0,CL m=-INF,CI t=0,CL s=0):P(p),Mx(m),T(t),S(s){F=0;}
I node operator + (Con node& o) Con
{return Mx>o.Mx?node(P,Mx,T+o.T,S+o.S):node(o.P,o.Mx,T+o.T,S+o.S);}//上传信息
I bool U(Con LL& x) {return Mx+x>=0?1:(Mx+=x,F+=x,S+=x*T,0);}//如果出现了非负数，返回1
}O[N<<2];
I void BF(CI x,Con LL& v,CI l,CI r,CI rt)//暴力修改
{
if(l==r) return (void)(O[rt]=node(0,-INF,1,v-O[rt].S));int mid=l+r>>1;PD(rt),//叶节点修改信息
x<=mid?(BF(x,v,LT),F5(rt<<1|1,mid+1,r,v)):(BF(x,v,RT),F5(rt<<1,l,mid,v)),PU(rt);//注意给另一子树打上修改标记
}
public:
I void Build(int *v,PT)//建树
{
if(l==r) return (void)(O[rt]=v[l]<0?node(l,v[l],-1,-v[l]):node(0,-INF,1,v[l]));//根据正负性确定初始信息
int mid=l+r>>1;Build(v,LT),Build(v,RT),PU(rt);
}
I void U(CI L,CI R,CI v,PT)//区间加法
{
if(L<=l&&r<=R) return (void)F5(rt,l,r,v);int mid=l+r>>1;
PD(rt),L<=mid&&(U(L,R,v,LT),0),R>mid&&(U(L,R,v,RT),0),PU(rt);
}
I LL Q(CI L,CI R,PT)//区间求和
{
if(L<=l&&r<=R) return O[rt].S;int mid=l+r>>1;PD(rt);
return (L<=mid?Q(L,R,LT):0)+(R>mid?Q(L,R,RT):0);
}
}S;
I void dfs1(CI x)
{
sz[x]=1;for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^f[x]&&
(
p[e[i].to]=p[f[e[i].to]=x]+1,dfs1(e[i].to),sz[x]+=sz[e[i].to],
sz[e[i].to]>sz[s[x]]&&(s[x]=e[i].to)
);
}
I void dfs2(CI x,CI t)
{
v[D[x]=++d]=a[x],tp[x]=t,s[x]&&(dfs2(s[x],t),0);
for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^f[x]&&e[i].to^s[x]&&(dfs2(e[i].to,e[i].to),0);
}
public:
I void Init() {dfs1(1),dfs2(1,1),S.Build(v);}
I void U(RI x,RI y,CI v)//树上路径修改
{
W(tp[x]^tp[y]) p[tp[x]]<p[tp[y]]&&swap(x,y),S.U(D[tp[x]],D[x],v),x=f[tp[x]];
D[x]>D[y]&&swap(x,y),S.U(D[x],D[y],v);
}
I LL Q(RI x,RI y)//树上路径询问绝对值和
{
RL t=0;W(tp[x]^tp[y]) p[tp[x]]<p[tp[y]]&&swap(x,y),t+=S.Q(D[tp[x]],D[x]),x=f[tp[x]];
return D[x]>D[y]&&swap(x,y),t+S.Q(D[x],D[y]);
}
}T;
int main()
{
RI Qt,i,op,x,y,z;for(F.read(n,Qt),i=1;i<=n;++i) F.read(a[i]);
for(i=1;i^n;++i) F.read(x,y),add(x,y),add(y,x);T.Init();
W(Qt--) F.read(op,x,y),op^2?F.read(z),T.U(x,y,z):F.writeln(T.Q(x,y));
return F.clear(),0;
}