我看看，我现在就发现了一个问题,修改不push_up
by xiao7_Mr_10_ @ 2023-12-15 19:33:22
调好了,你太粗心了,push_up没写然后你那个分类讨论有问题,我给你重写了,代码没多少变动:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int inf=1e9+7;
vector<int>e[N];
struct Tree{
long long maxx,minn,max1/*l~r*/,max2/*r~l*/,o;
}t[N];
long long f[N],son[N],w[N],wd[N],id[N],siz[N],top[N],dep[N],cnt;
void dfs1(long long x,long long fa){
f[x]=fa;
dep[x]=dep[fa]+1;
siz[x]=1;
for(long long i=0;i<e[x].size();i++){
if(e[x][i]!=fa){
dfs1(e[x][i],x);
if(siz[e[x][i]]>siz[son[x]])son[x]=e[x][i];
siz[x]+=siz[e[x][i]];
}
}
}
void dfs2(long long x,long long tp){
top[x]=tp;
cnt++;
id[x]=cnt;
wd[cnt]=w[x];
if(son[x]==0)return;
dfs2(son[x],tp);
for(long long i=0;i<e[x].size();i++){
if(e[x][i]!=f[x]&&e[x][i]!=son[x]){
dfs2(e[x][i],e[x][i]);
}
}
}
void updata(long long z){
t[z].minn=min(t[z<<1].minn,t[z<<1|1].minn);
t[z].maxx=max(t[z<<1].maxx,t[z<<1|1].maxx);
t[z].max1=max(t[z<<1].max1,max(t[z<<1|1].max1,t[z<<1|1].maxx-t[z<<1].minn));
t[z].max2=max(t[z<<1].max2,max(t[z<<1|1].max2,t[z<<1].maxx-t[z<<1|1].minn));
}
void build(long long l,long long r,long long z){
if(l==r){
t[z].minn=wd[l];
t[z].maxx=wd[l];
return;
}
long long mid=(l+r)>>1;
build(l,mid,z<<1);
build(mid+1,r,z<<1|1);
updata(z);
}
void push_down(long long z){
if(t[z].o!=0){
t[z<<1].o+=t[z].o;
t[z<<1|1].o+=t[z].o;
t[z<<1].maxx+=t[z].o;
t[z<<1|1].maxx+=t[z].o;
t[z<<1].minn+=t[z].o;
t[z<<1|1].minn+=t[z].o;
t[z].o=0;
}
}
void xg(long long l,long long r,long long x,long long y,long long z,long long k){
if(l<=x&&y<=r){
t[z].o+=k;
t[z].minn+=k;
t[z].maxx+=k;
return;
}
push_down(z);
long long mid=(x+y)>>1;
if(mid>=l)xg(l,r,x,mid,z<<1,k);
if(mid<r)xg(l,r,mid+1,y,z<<1|1,k);
updata(z);
}
long long jc(long long l,long long r,long long x,long long z){//查询最小值?
if(l==r&&l==x){
return t[z].minn;
}
if(l!=r)push_down(z);
long long mid=(l+r)>>1;
if(mid>=x)return jc(l,mid,x,z<<1);
else return jc(mid+1,r,x,z<<1|1);
}
Tree cx(long long l,long long r,long long x,long long y,long long z){//查询
if(l<=x&&y<=r){
return t[z];
}
if(l!=r)push_down(z);
long long mid=(x+y)>>1;
if(mid>=l&&mid<r){
Tree a=cx(l,r,x,mid,z<<1);//l
Tree b=cx(l,r,mid+1,y,z<<1|1);//r
Tree ans;
ans.maxx=max(a.maxx,b.maxx);
ans.minn=min(a.minn,b.minn);
ans.max1=max(a.max1,max(b.max1,b.maxx-a.minn));
ans.max2=max(a.max2,max(b.max2,a.maxx-b.minn));
return ans;
}
else if(mid>=l)return cx(l,r,x,mid,z<<1);
else if(mid<r)return cx(l,r,mid+1,y,z<<1|1);
}
void lcaxg(long long x,long long y,long long k){//修改
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
xg(id[top[x]],id[x],1,cnt,1,k);
x=f[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
xg(id[x],id[y],1,cnt,1,k);
}
long long n;
long long lcacx(long long x,long long y){
long long qd=x,zd=y;//起点，终点
Tree l,r;
//不是左右，只是想象成左是开头右是结尾,(不要在意变量名）
//服了,线段树这么写我也不说什么,忍不了了,改成l和r了
l.max1=l.max2=0,l.minn=inf,l.maxx=-inf;
r=l;//初始化,个人习惯
//你分类讨论太丑了,我重新写了,相信你不敢有意见
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
Tree ans=cx(id[top[y]],id[y],1,n,1);
r.max1=max(max(ans.max1,r.max1),r.maxx-ans.minn);
r.max2=max(max(ans.max2,r.max2),ans.maxx-r.minn);
r.maxx=max(r.maxx,ans.maxx);
r.minn=min(r.minn,ans.minn);
y=f[top[y]];
}
else{
Tree ans=cx(id[top[x]],id[x],1,n,1);
l.max1=max(max(ans.max1,l.max1),l.maxx-ans.minn);
l.max2=max(max(ans.max2,l.max2),ans.maxx-l.minn);
l.maxx=max(l.maxx,ans.maxx);
l.minn=min(l.minn,ans.minn);
x=f[top[x]];
}
}
if(dep[x]<dep[y]){
Tree ans=cx(id[x],id[y],1,n,1);
r.max1=max(max(ans.max1,r.max1),r.maxx-ans.minn);
r.max2=max(max(ans.max2,r.max2),ans.maxx-r.minn);
r.maxx=max(r.maxx,ans.maxx);
r.minn=min(r.minn,ans.minn);
}
else{
Tree ans=cx(id[y],id[x],1,n,1);
l.max1=max(max(ans.max1,l.max1),l.maxx-ans.minn);
l.max2=max(max(ans.max2,l.max2),ans.maxx-l.minn);
l.maxx=max(l.maxx,ans.maxx);
l.minn=min(l.minn,ans.minn);
}
int ans=max(max(l.max2,r.max1),r.maxx-l.minn);
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(long long i=1;i<=n;i++)cin>>w[i];
for(long long i=1;i<n;i++){
long long x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs1(1,0);
dfs2(1,1);
build(1,n,1);
long long q;
cin>>q;
for(long long i=1;i<=q;i++){
long long a,b,u;
cin>>a>>b>>u;
lcaxg(a,b,u);
cout << lcacx(a,b) <<"\n";
}
return 0;
}
```
by xiao7_Mr_10_ @ 2023-12-15 19:52:13
@[xiao7_Mr_10_](/user/961149) 谢谢，我确实太粗心了。
拜
by wang_ly_ly @ 2023-12-17 13:35:07
@[xiao7_Mr_10_](/user/961149) 为什么修改要push_up呢？
我从来不push_up
拜
by wang_ly_ly @ 2023-12-17 13:36:52
@[wang_ly_ly](/user/748723) 你区间修改不push_up,想上天?
by xiao7_Mr_10_ @ 2023-12-17 14:22:37
@[xiao7_Mr_10_](/user/961149) 那为什么我以前从来不写呢？
而且我以前又不是没a过线段树
by wang_ly_ly @ 2023-12-17 14:38:27
@[wang_ly_ly](/user/748723) 区间修改不push_up?标记永久化?这题不行的吧
by xiao7_Mr_10_ @ 2023-12-17 16:48:09
@[xiao7_Mr_10_](/user/961149) 为什么cx里有push_up会RE??
by wang_ly_ly @ 2023-12-17 23:18:34