#树链剖分，线段树#SP6779 GSS7

线段树#SP6779 GSS7"/>

#树链剖分，线段树#SP6779 GSS7

题目

在一棵 n n n个节点的树上满足两种操作：

1. 把树上一条简单路径展开成一个数列，求这个数列的最大子段和（可以为空）
2. 把树上一条简单路径上的点权同时加上一个值

分析

这道题其实也就是最大子段和的树上版，大同小异，妙不可言
特别是求答案的部分，由于是一条链，所以必须用两个东东去分别存储最大前缀和、最大后缀和以及最大子段和，等到最后再合并，还是我太菜了

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
inline signed iut(){rr int ans=0,f=1; rr char c=getchar();while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans*f;
}
inline void print(int ans){if (ans<0) putchar('-'),ans=-ans;if (ans>9) print(ans/10);putchar(ans%10+48);
}
inline signed max(int a,int b){return a>b?a:b;}
const int N=100011; struct node{int y,next;}e[N<<1];
struct xds{int lmax,rmax,lazy,w,sum;inline void pro(){lmax=rmax=w=sum=0,lazy=-10001;}
}b[N<<2];
int a[N],A[N],ls[N],dep[N],top[N],dfn[N],n,fat[N],son[N],big[N],K=1,tot;
inline xds comb(xds fir,xds sec){rr xds ans;ans.sum=fir.sum+sec.sum;ans.lmax=max(fir.lmax,fir.sum+sec.lmax);ans.rmax=max(fir.rmax+sec.sum,sec.rmax);ans.w=max(max(fir.w,sec.w),fir.rmax+sec.lmax);ans.lazy=-10001;return ans;
}
inline void paste(int k,int z1,int z2){b[k].w=b[k].lmax=b[k].rmax=max(b[k].sum=z1,0),b[k].lazy=z2;}
inline void build(int k,int l,int r){if (l==r) {paste(k,a[l],-10001); return;}rr int mid=(l+r)>>1;build(k<<1,l,mid),build(k<<1|1,mid+1,r);b[k]=comb(b[k<<1],b[k<<1|1]);
}
inline void pup(int k,int l,int r,int z){paste(k,(r-l+1)*z,z);}
inline void pdown(int k,int l,int r){if (b[k].lazy==-10001) return;rr int mid=(l+r)>>1;pup(k<<1,l,mid,b[k].lazy),pup(k<<1|1,mid+1,r,b[k].lazy),b[k].lazy=-10001; 
}
inline void update(int k,int l,int r,int x,int y,int z){if (l==x&&r==y) {pup(k,l,r,z); return;}pdown(k,l,r); rr int mid=(l+r)>>1;if (y<=mid) update(k<<1,l,mid,x,y,z);else if (x>mid) update(k<<1|1,mid+1,r,x,y,z);else update(k<<1,l,mid,x,mid,z),update(k<<1|1,mid+1,r,mid+1,y,z);b[k]=comb(b[k<<1],b[k<<1|1]);
}
inline xds query(int k,int l,int r,int x,int y){if (l==x&&r==y) return b[k];pdown(k,l,r); rr int mid=(l+r)>>1;if (y<=mid) return query(k<<1,l,mid,x,y);else if (x>mid) return query(k<<1|1,mid+1,r,x,y);rr xds t1=query(k<<1,l,mid,x,mid),t2=query(k<<1|1,mid+1,r,mid+1,y);return comb(t1,t2);
}
inline void Update(int x,int y,int z){for (;top[x]!=top[y];x=fat[top[x]]){if (dep[top[x]]<dep[top[y]]) x^=y,y^=x,x^=y;update(1,1,n,dfn[top[x]],dfn[x],z);}if (dep[x]>dep[y]) x^=y,y^=x,x^=y;update(1,1,n,dfn[x],dfn[y],z);
}
inline signed Query(int x,int y){rr xds fir,sec; fir.pro(),sec.pro();for (;top[x]!=top[y];){if (dep[top[x]]<dep[top[y]])sec=comb(query(1,1,n,dfn[top[y]],dfn[y]),sec),y=fat[top[y]];else fir=comb(query(1,1,n,dfn[top[x]],dfn[x]),fir),x=fat[top[x]];}if (dep[x]<dep[y]) sec=comb(query(1,1,n,dfn[x],dfn[y]),sec);else fir=comb(query(1,1,n,dfn[y],dfn[x]),fir);swap(fir.lmax,fir.rmax),fir=comb(fir,sec);return fir.w;
}
inline void dfs1(int x,int fa){dep[x]=dep[fa]+1,fat[x]=fa,son[x]=1;for (rr int i=ls[x],mson=-1;i;i=e[i].next)if (e[i].y!=fa){dfs1(e[i].y,x),son[x]+=son[e[i].y];if (son[e[i].y]>mson) big[x]=e[i].y,mson=son[e[i].y];}
}
inline void dfs2(int x,int linp){dfn[x]=++tot,a[tot]=A[x],top[x]=linp;if (!big[x]) return; dfs2(big[x],linp);for (rr int i=ls[x];i;i=e[i].next)if (e[i].y!=fat[x]&&e[i].y!=big[x]) dfs2(e[i].y,e[i].y);
}
signed main(){n=iut();for (rr int i=1;i<=n;++i) A[i]=iut();for (rr int i=1;i<n;++i){rr int x=iut(),y=iut();e[++K]=(node){y,ls[x]},ls[x]=K;e[++K]=(node){x,ls[y]},ls[y]=K;}dfs1(1,0),dfs2(1,1),build(1,1,n);for (rr int m=iut();m;--m){rr int opt=iut();if (opt&1){print(Query(iut(),iut())),putchar(10);continue;}rr int x=iut(),y=iut(),w=iut();Update(x,y,w);}return 0;
}