Description
给定一棵树,设计数据结构支持以下操作
1 u v d 表示将路径 (u,v) 加d
2 u v 表示询问路径 (u,v) 上点权绝对值的和
n,m <= 10^5 0<= d,|a_i|<= 10^8
树链剖分+线段树
由于d一直是正的，所以负数只有在开始的一段时间内是负的。
那么可以在区间加d出现负数变成正数情况的时候进行暴力重构，这种操作的次数不超过n次，复杂度nlogn。
需要维护区间内的非负数的个数（用于给区间加d的时候更新绝对值的和），区间内的最大的负数（判断重构），区间的绝对值的和。
然后线段树的部分就结束了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 101000
using namespace std;
typedef long long ll;
int n,m,w[101000];
inline void read(int &x)
{
x=0;int f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
x*=f;
}
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int top[N],tid[N],fa[N],son[N],siz[N],tr[N],deep[N],tot;
void dfs1(int x,int pre)
{
siz[x]=1; fa[x]=pre; deep[x]=deep[pre]+1;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre)
{
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
}
}
void dfs2(int x,int anc)
{
tid[x]=++tot; top[x]=anc; tr[tot]=w[x];
if(son[x]) dfs2(son[x],anc);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
}
int si[N<<2],def[N<<2];
ll sum[N<<2],lz[N<<2];
void pushup(int pos)
{
def[pos]=0;
if(def[pos<<1]) def[pos]=def[pos<<1];
if(def[pos<<1|1]) def[pos]=(def[pos])?max(def[pos],def[pos<<1|1]):def[pos<<1|1];
si[pos]=si[pos<<1]+si[pos<<1|1];
sum[pos]=sum[pos<<1]+sum[pos<<1|1];
}
void pushdown(int pos,int l,int r,bool fl1,bool fl2)
{
if(lz[pos])
{
int mid=l+r>>1;
if(fl1)
{
if(def[pos<<1]) def[pos<<1]+=lz[pos];
sum[pos<<1]+=1ll* (si[pos<<1]*2 - (mid-l+1)) *lz[pos];
lz[pos<<1]+=lz[pos];
}
if(fl2)
{
if(def[pos<<1|1]) def[pos<<1|1]+=lz[pos];
sum[pos<<1|1]+=1ll* (si[pos<<1|1]*2 - (r-mid)) *lz[pos];
lz[pos<<1|1]+=lz[pos];
}
lz[pos]=0;
}
}
void build(int pos,int l,int r)
{
if(l==r)
{
if(tr[l]<0) def[pos]=tr[l],sum[pos]=-tr[l];
else si[pos]=1,sum[pos]=tr[l];
return ;
}
int mid=l+r>>1;
build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
pushup(pos);
}
void rebuild(int pos,int l,int r,ll z)//当前区间应当加上一个z，然而没有加，重构当前区间。
{
if(l==r) {sum[pos]=def[pos]+z; def[pos]=0; si[pos]=1; return;}
int mid=l+r>>1; z+=lz[pos]; lz[pos]=z;
if(def[pos<<1]&&def[pos<<1]+z>=0&&def[pos<<1|1]&&def[pos<<1|1]+z>=0)
{
lz[pos]=0;
rebuild(pos<<1,l,mid,z);
rebuild(pos<<1|1,mid+1,r,z);
}
else if(def[pos<<1]&&def[pos<<1]+z>=0)
{
pushdown(pos,l,r,0,1);
rebuild(pos<<1,l,mid,z);
}
else if(def[pos<<1|1]&&def[pos<<1|1]+z>=0)
{
pushdown(pos,l,r,1,0);
rebuild(pos<<1|1,mid+1,r,z);
}
pushup(pos);
}
void fix(int pos,int l,int r,int x,int y,int z)
{
if(x<=l&&y>=r)
{
if(def[pos]&&def[pos]+z>=0) rebuild(pos,l,r,z);
else
{
if(def[pos]) def[pos]+=z; lz[pos]+=z;
sum[pos]+=1ll*(si[pos]*2-(r-l+1))*z;
}
return ;
}
int mid=l+r>>1; pushdown(pos,l,r,1,1);
if(y<=mid) fix(pos<<1,l,mid,x,y,z);
else if(x>mid) fix(pos<<1|1,mid+1,r,x,y,z);
else fix(pos<<1,l,mid,x,y,z),fix(pos<<1|1,mid+1,r,x,y,z);
pushup(pos);
}
ll query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return sum[pos];
int mid=l+r>>1; pushdown(pos,l,r,1,1);
if(y<=mid) return query(pos<<1,l,mid,x,y);
else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
else return query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y);
}
void Fix()
{
int x,y,z; scanf("%d%d%d",&x,&y,&z);
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
fix(1,1,n,tid[top[x]],tid[x],z);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
fix(1,1,n,tid[x],tid[y],z);
}
void Query()
{
int x,y; ll ans=0; scanf("%d%d",&x,&y);
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=query(1,1,n,tid[top[x]],tid[x]);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
ans+=query(1,1,n,tid[x],tid[y]);
printf("%lld\n",ans);
}
int main()
{
scanf("%d%d",&n,&m); int i,x,y;
for(i=1;i<=n;++i) read(w[i]);
for(i=1;i!=n;++i)
{
read(x); read(y);
add(x,y); add(y,x);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(m--)
{
scanf("%d",&x);
if(x==1) Fix();
else Query();
}
return 0;
}