Lvat_s Blog

嗯……

因为每次加上的d都是正值，那么最多只有n次从负数到非负数的转换

所以我们分正负数分别维护，统计贡献时加一加就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
const int N=100005;
const long long INF=999999999999999ll;
 
int n,m,dep[N],siz[N],son[N],fa[N],id[N],pre[N],segn,en,h[N],top[N];
long long a[N];
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}
 
struct SegTree{
int l,r;
long long s1,s2,tag,mx,sn1,sn2,sum;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag+=tree[rt].tag;
    tree[rt<<1].s1+=tree[rt<<1].sn1*tree[rt].tag;
    tree[rt<<1].s2+=tree[rt<<1].sn2*tree[rt].tag;
    tree[rt<<1].sum=tree[rt<<1].s1-tree[rt<<1].s2;
    tree[rt<<1].mx+=tree[rt].tag;
    tree[rt<<1|1].tag+=tree[rt].tag;
    tree[rt<<1|1].s1+=tree[rt<<1|1].sn1*tree[rt].tag;
    tree[rt<<1|1].s2+=tree[rt<<1|1].sn2*tree[rt].tag;
    tree[rt<<1|1].sum=tree[rt<<1|1].s1-tree[rt<<1|1].s2;
    tree[rt<<1|1].mx+=tree[rt].tag;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx);
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
tree[rt].sn1=tree[rt<<1].sn1+tree[rt<<1|1].sn1;
tree[rt].sn2=tree[rt<<1].sn2+tree[rt<<1|1].sn2;
tree[rt].s1=tree[rt<<1].s1+tree[rt<<1|1].s1;
tree[rt].s2=tree[rt<<1].s2+tree[rt<<1|1].s2;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
    if(a[pre[l]]>=0){
        tree[rt].s1+=a[pre[l]];
        tree[rt].sn1=1;
        tree[rt].mx=-INF;
    }
    else {
        tree[rt].s2+=a[pre[l]];
        tree[rt].sn2=1;
        tree[rt].mx=a[pre[l]];
    }
    tree[rt].sum=tree[rt].s1-tree[rt].s2;
    return;
}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Ex_Modify(int rt,int d){
if(tree[rt].l==tree[rt].r){
    tree[rt].sn1=1;
    tree[rt].sn2=0;
    tree[rt].s1=tree[rt].s2+d;
    tree[rt].s2=0;
    tree[rt].mx=-INF;
    tree[rt].sum=tree[rt].s1;
    return;
}
Pushdown(rt);
if(tree[rt<<1].mx+d>0)Ex_Modify(rt<<1,d);
else {
    tree[rt<<1].tag+=d;
    tree[rt<<1].s1+=tree[rt<<1].sn1*d;
    tree[rt<<1].s2+=tree[rt<<1].sn2*d;
    tree[rt<<1].sum=tree[rt<<1].s1-tree[rt<<1].s2;
    tree[rt<<1].mx+=d;
}
if(tree[rt<<1|1].mx+d>0)Ex_Modify(rt<<1|1,d);
else {
    tree[rt<<1|1].tag+=d;
    tree[rt<<1|1].s1+=tree[rt<<1|1].sn1*d;
    tree[rt<<1|1].s2+=tree[rt<<1|1].sn2*d;
    tree[rt<<1|1].sum=tree[rt<<1|1].s1-tree[rt<<1|1].s2;
    tree[rt<<1|1].mx+=d;
}
Pushup(rt);
}
 
void Modify(int rt,int l,int r,long long d){
if(l<=tree[rt].l && tree[rt].r<=r){
    if(tree[rt].mx+d>0){Ex_Modify(rt,d);}
    else {tree[rt].tag+=d;tree[rt].mx+=d;tree[rt].s1+=d*tree[rt].sn1;tree[rt].s2+=d*tree[rt].sn2;tree[rt].sum=tree[rt].s1-tree[rt].s2;}
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Modify(rt<<1,l,r,d);
if(r>mid)Modify(rt<<1|1,l,r,d);
Pushup(rt);
}
 
long long Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].sum;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(r<=mid)return Query(rt<<1,l,r);
else if(l>mid)return Query(rt<<1|1,l,r);
else return Query(rt<<1,l,r)+Query(rt<<1|1,l,r);
}
 
void dfs1(int u,int fat){
dep[u]=dep[fat]+1;
fa[u]=fat;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fat)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u] || v==son[u])continue;
    dfs2(v,v);
}
}
 
void Update(int u,int v,long long d){
int topu=top[u],topv=top[v];
while(topu!=topv){
    if(dep[topu]<dep[topv]){swap(topu,topv);swap(u,v);}
    Modify(1,id[topu],id[u],d);
    u=fa[topu];
    topu=top[u];
}
if(dep[u]>dep[v])swap(u,v);
Modify(1,id[u],id[v],d);
}
 
long long Ask(int u,int v){
int topu=top[u],topv=top[v];
long long Sum=0;
while(topu!=topv){
    if(dep[topu]<dep[topv]){swap(topu,topv);swap(u,v);}
    Sum+=Query(1,id[topu],id[u]);
    u=fa[topu];
    topu=top[u];
}
if(dep[u]>dep[v])swap(u,v);
return Sum+Query(1,id[u],id[v]);
}
 
int main(){
freopen("4127.in","r",stdin);
freopen("4127.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    AddEdge(u,v);
    AddEdge(v,u);
}
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,u,v;
    long long d;
    scanf("%d %d %d",&opt,&u,&v);
    if(opt==1){scanf("%lld",&d);Update(u,v,d);}
    if(opt==2)printf("%lld\n",Ask(u,v));
}
return 0;
}