题目
SP6779 GSS7 - Can you answer these queries VII
分析
明显可以树剖/(LCT)，转化成经典问题：区间动态查询最大子段和。
树剖的话无非是每次求完了还要把 (log) 个区间再拼起来。
(LCT) 的话就只拼数据结构上的了（指 (Splay) 维护序列的套路）。
代码
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=1e5+5,null=114514;
struct Edge{
int to,next;
}Edge[N<<1];
struct SGTree{
int sum,siz,lazy,l_Max,r_Max,Max;
SGTree(){sum=siz=l_Max=r_Max=Max=0;lazy=-null;}
}t[N<<2];
int n,m,idx,DFN;
int val[N],Val[N];
int dep[N],top[N],siz[N],son[N],head[N],fa[N],id[N];
inline void add(int u,int v){idx++,Edge[idx].to=v,Edge[idx].next=head[u],head[u]=idx;}
inline void dfs1(int x,int f){
fa[x]=f,dep[x]=dep[f]+1,siz[x]=1;
for(int i=head[x];i;i=Edge[i].next){
if(Edge[i].to==f) continue;
dfs1(Edge[i].to,x);
if(siz[Edge[i].to]>siz[son[x]]) son[x]=Edge[i].to;
siz[x]+=siz[Edge[i].to];
}
}
inline void dfs2(int x,int Fa){
top[x]=Fa,id[x]=++DFN,Val[DFN]=val[x];
if(!son[x]) return ;dfs2(son[x],Fa);
for(int i=head[x];i;i=Edge[i].next){
if(Edge[i].to==fa[x] || Edge[i].to==son[x]) continue;
dfs2(Edge[i].to,Edge[i].to);
}
}
inline void Pushup(int x){
t[x].sum=t[x<<1].sum+t[x<<1|1].sum,
t[x].l_Max=max(t[x<<1].l_Max,t[x<<1].sum+t[x<<1|1].l_Max);
t[x].r_Max=max(t[x<<1|1].r_Max,t[x<<1|1].sum+t[x<<1].r_Max);
t[x].Max=max(t[x<<1].r_Max+t[x<<1|1].l_Max,max(t[x<<1].Max,t[x<<1|1].Max));
}
inline void PushDown(int x){
t[x<<1].sum=t[x<<1].siz*t[x].lazy;
t[x<<1|1].sum=t[x<<1|1].siz*t[x].lazy;
t[x<<1].Max=t[x<<1].l_Max=t[x<<1].r_Max=max(0,t[x<<1].sum);
t[x<<1|1].Max=t[x<<1|1].l_Max=t[x<<1|1].r_Max=max(0,t[x<<1|1].sum);
t[x<<1].lazy=t[x<<1|1].lazy=t[x].lazy;
t[x].lazy=-null;
}
inline SGTree Merge(SGTree a,SGTree b){
SGTree tmp;
tmp.sum=a.sum+b.sum;
tmp.l_Max=max(a.l_Max,a.sum+b.l_Max);
tmp.r_Max=max(b.r_Max,b.sum+a.r_Max);
tmp.Max=max(max(a.Max,b.Max),a.r_Max+b.l_Max);
tmp.lazy=-null;
return tmp;
}
inline void Build(int x,int l,int r){
t[x].siz=r-l+1;
if(l==r){
t[x].sum=t[x].Max=t[x].l_Max=t[x].r_Max=Val[l];
return ;
}
const int Mid=l+r>>1;
Build(x<<1,l,Mid),Build(x<<1|1,Mid+1,r);
Pushup(x);
return ;
}
inline void Modify(int x,int l,int r,int L,int R,int k){
if(l>=L && r<=R){
t[x].lazy=k;
t[x].sum=t[x].siz*k;
t[x].Max=t[x].l_Max=t[x].r_Max=max(0,t[x].sum);
return ;
}
if(t[x].lazy!=-null) PushDown(x);
const int Mid=l+r>>1;
if(R<=Mid) Modify(x<<1,l,Mid,L,R,k);
else if(L>Mid) Modify(x<<1|1,Mid+1,r,L,R,k);
else Modify(x<<1,l,Mid,L,R,k),Modify(x<<1|1,Mid+1,r,L,R,k);
Pushup(x);
}
inline SGTree Query(int x,int l,int r,int L,int R){
if(l>=L && r<=R) return t[x];
if(t[x].lazy!=-null) PushDown(x);
const int Mid=l+r>>1;
if(R<=Mid) return Query(x<<1,l,Mid,L,R);
else if(L>Mid) return Query(x<<1|1,Mid+1,r,L,R);
else return Merge(Query(x<<1,l,Mid,L,R),Query(x<<1|1,Mid+1,r,L,R));
}
inline int RoadQuery(int x,int y){
SGTree L,R;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) {
R=Merge(Query(1,1,n,id[top[y]],id[y]),R);
y=fa[top[y]];
}
else {
L=Merge(Query(1,1,n,id[top[x]],id[x]),L);
x=fa[top[x]];
}
}
if(dep[x]>dep[y]) L=Merge(Query(1,1,n,id[y],id[x]),L);
else R=Merge(Query(1,1,n,id[x],id[y]),R);
swap(L.l_Max,L.r_Max);
return Merge(L,R).Max;
}
inline void RoadModify(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
Modify(1,1,n,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
Modify(1,1,n,id[x],id[y],k);
return ;
}
signed main(){
read(n);
for(int i=1;i<=n;i++) read(val[i]);
for(int i=1;i<n;i++){
int u,v;read(u),read(v);
add(u,v),add(v,u);
}
dfs1(1,0),dfs2(1,1),Build(1,1,n);
read(m);
for(int i=1;i<=m;i++){
int op;read(op);
if(op==1){
int x,y;read(x),read(y);
write(RoadQuery(x,y)),putchar('
');
}
else{
int x,y,k;
read(x),read(y),read(k);
RoadModify(x,y,k);
}
}
return 0;
}