r 没赋初值 pushup 也写错了 query2的返回值也有点问题 别的我再看看
by Zzzcr @ 2023-12-25 20:40:17
qry2跳重链也写错了，贴个代码吧我
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k,r,p,vst;
ll a[200005];
int fa[200005],hs[200005],sz[200005],top[200005],dfn[200005],rdfn[200005],dep[200005];
vector<int>G[200005];
void dfs(int u,int fat) {
fa[u]=fat;
sz[u]=1;
dep[u]=dep[fat]+1;
for(auto &v:G[u]) {
if(v==fat)continue;
dfs(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[hs[u]])hs[u]=v;
}
}
void cut(int u,int tp) {
dfn[u]=++vst;
rdfn[vst]=u;
top[u]=tp;
if(hs[u]) {
cut(hs[u],tp);
for(auto &v:G[u])if(v!=fa[u]&&v!=hs[u])cut(v,v);
}
}
ll tr[800020],trr[800020];
void pup(int u) {
tr[u]=tr[u<<1]+tr[u<<1|1];
trr[u]=max(trr[u<<1],trr[u<<1|1]);
}
void build(int u,int le,int ri) {
if(le==ri) {
tr[u]=trr[u]=a[rdfn[le]];
return;
}
int mid=(le+ri)>>1;
build(u<<1,le,mid);
build(u<<1|1,mid+1,ri);
pup(u);
}
bool inr(int le,int ri,int L,int R) {
return (L<=le)&&(ri<=R);
}
bool otr(int le,int ri,int L,int R) {
return (le>R)||(ri<L);
}
ll query(int u,int le,int ri,int L,int R) {
if(inr(le,ri,L,R))return tr[u];
else if(!otr(le,ri,L,R)) {
int mid=(le+ri)>>1;
return (query(u<<1,le,mid,L,R)+query(u<<1|1,mid+1,ri,L,R));
}
return 0;
}
ll qry(int x,int y) {
ll ans=0;
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans+=query(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
return (ans+query(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])));
}
ll query2(int u,int le,int ri,int L,int R) {
if(inr(le,ri,L,R))return trr[u];
else if(!otr(le,ri,L,R)) {
int mid=(le+ri)>>1;
return max(query2(u<<1,le,mid,L,R),query2(u<<1|1,mid+1,ri,L,R));
}
return -3e4;
}
ll qry2(int x,int y) {
ll ans=INT_MIN;
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=max(ans,query2(1,1,n,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
return max(ans,query2(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])));
}
void update(int u,int le,int ri,int ft,ll x) {
int mid=(le+ri)>>1;
if(le==ri){
tr[u]=trr[u]=x;
return;
}
if(ft<=mid)update(u<<1,le,mid,ft,x);
else update(u<<1|1,mid+1,ri,ft,x);
pup(u);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1; i<n; i++) {
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1; i<=n; i++)cin>>a[i];
cin>>m;
for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end(),[](int x,int y){return a[x]<a[y];});
dfs(1,0);
cut(1,1);
build(1,1,n);
while(m--) {
string ord;
cin>>ord;
if(ord=="QSUM"){
int u,v;
cin>>u>>v;
cout<<qry(u,v)<<'\n';
}else if(ord=="CHANGE"){
int u,v;
cin>>u>>v;
update(1,1,n,dfn[u],v);
}else if(ord=="QMAX"){
int u,v;
cin>>u>>v;
cout<<qry2(u,v)<<'\n';
}
}
}
```
by Zzzcr @ 2023-12-25 20:42:51
@[爱肝大模拟的tlxjy](/user/482610)
by Zzzcr @ 2023-12-25 20:43:12