query2里面递归的时候写成query了
by Zzzcr @ 2024-02-20 14:50:55
pushup里面也是类似的，max从两个子节点max转移 @[a_good_boy](/user/1025679)
by Zzzcr @ 2024-02-20 14:56:05
ac代码
```cpp
#include <bits/stdc++.h>
#define Y ios::sync_with_stdio(false);
#define X cin.tie(0); cout.tie(0);
#define f first
#define s second
#define il inline
#define re register
#define co const
#define PII pair<int,int>
#define bit(x) (x&-x)
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
il int read(){
int x=0,f=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')f=-1;
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
il void w(int x) {
if(x<0)x=-x,putchar('-');
if(x>9)w(x/10);
putchar(x%10+'0');
}
const int N=1e5+10,INF=0x3f3f3f3f;
int ww[N],n,m,a[N],cnt;
int son[N],id[N],f[N],h[N],s[N],top[N];
int e,to[N<<1],nex[N<<1],hd[N];
void addd(int x,int y){
to[++e]=y;
nex[e]=hd[x];
hd[x]=e;
}
struct tre{int v,ma;}t[N<<2];
struct tree{
il void push_up(re int p){
t[p].v=(t[p<<1].v+t[p<<1|1].v);
t[p].ma=max(t[p<<1].ma,t[p<<1|1].ma);
}
il void build(re int p,re int pl,re int pr){
if(pl==pr){t[p].v=t[p].ma=ww[a[pl]];return;}
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
push_up(p);
}
il void update(int p,re int l,re int r,re int tp,re int d){
if(l==r){t[p].v=t[p].ma=d;return;}
int mid=(l+r)>>1;
if(tp<=mid) update(ls(p),l,mid,tp,d);
else update(rs(p),mid+1,r,tp,d);
push_up(p);
}
il int query(co int l,co int r,co int p,co int L,co int R){
if(L<=l&&r<=R) return t[p].v;
int res=0,mid=(l+r)>>1;
if(L<=mid) res=(res+query(l,mid,ls(p),L,R));
if(R>mid) res=(res+query(mid+1,r,rs(p),L,R));
return res;
}
il int query2(co int l,co int r,co int p,co int L,co int R){
if(L<=l&&r<=R) return t[p].ma;
int res=-INF,mid=(l+r)>>1;
if(L<=mid) res=max(res,query2(l,mid,ls(p),L,R));
if(R>mid) res=max(res,query2(mid+1,r,rs(p),L,R));
return res;
}
}tr;
il void dfs1(re int x){
s[x]=1;
for(int i=hd[x]; i; i=nex[i]){
int u=to[i];
if(h[u]) continue;
h[u]=h[x]+1;
f[u]=x;
dfs1(u);
s[x]+=s[u];
if(!son[x]||s[u]>s[son[x]]) son[x]=u;
}
}
il void dfs2(re int x,re int tof){
id[x]=++cnt;
a[cnt]=x;
top[x]=tof;
if(!son[x]) return;
dfs2(son[x],tof);
for(int i=hd[x]; i; i=nex[i]){
int u=to[i];
if(u!=f[x]&&u!=son[x])
dfs2(u,u);
}
}
il int tqu(re int x,re int y){
int ans=0;
while(top[x]!=top[y]){
if(h[top[x]]<h[top[y]]) swap(x,y);
ans=(ans+tr.query(1,n,1,id[top[x]],id[x]));
x=f[top[x]];
}
if(h[x]>h[y]) swap(x,y);
return ans=(ans+tr.query(1,n,1,id[x],id[y]));
}
il int tqu2(re int x,re int y){
int ans=-INF;
while(top[x]!=top[y]){
if(h[top[x]]<h[top[y]]) swap(x,y);
ans=max(ans,tr.query2(1,n,1,id[top[x]],id[x]));
x=f[top[x]];
}
if(h[x]>h[y]) swap(x,y);
return ans=max(ans,tr.query2(1,n,1,id[x],id[y]));
}
signed main(){
n=read();
string op;
re int x,y;
for(re int i=1; i<n; i++){x=read(),y=read();addd(x,y);addd(y,x);}
for(re int i=1; i<=n; i++) ww[i]=read();
h[1]=1;
dfs1(1);
dfs2(1,1);
tr.build(1,1,n);
m=read();
while(m--){
cin>>op,x=read();y=read();
if(op=="CHANGE") tr.update(1,1,n,id[x],y);
else if(op=="QMAX") cout<<tqu2(x,y)<<"\n";
else if(op=="QSUM") cout<<tqu(x,y)<<"\n";
}
return 0;
}
```
by Zzzcr @ 2024-02-20 14:57:01
谢谢大佬，已关注
by a_good_boy @ 2024-02-20 15:15:23