@[Steve_xh](/user/639198) 首先,dfs2好像求错了,不是这样写的吗
```c
void dfs2(int now,int t){
seg[id[now]=++cntseg]=now;
top[now]=t;
if(son[now])dfs2(son[now],t);
for(int i=head[now];i;i=e[i].next)
if(e[i].to!=f[now]&&e[i].to!=son[now])
dfs2(e[i].to,e[i].to);
}
```
~~其次我还没看~~
by YC_George @ 2023-12-22 15:55:50
@[YC_George](/user/1004860) ooo对哦忘了没儿子了,thx
by Steve_xh @ 2023-12-22 15:59:25
@[YC_George](/user/1004860) ~~但是好像样例还没过~~
by Steve_xh @ 2023-12-22 16:01:30
@[Steve_xh](/user/639198) 等我看看
by YC_George @ 2023-12-22 16:10:08
首先 ``if(t[x].l>=l&&r<=t[x].r)``
有问题hh
by __Aaaaaaaa @ 2023-12-22 16:10:43
还有第47行改成``t[x].sum=t[x].maxn=a[seg[l]];``
by __Aaaaaaaa @ 2023-12-22 16:14:19
这下就行了,博主自己看吧
```
#include<bits/stdc++.h>
using namespace std;
int n,q,head[30005],a[30005],s[30005],f[30005],dep[30005];
int son[30005],top[30005],seg[30005],id[30005],cnt=0,cntseg=cnt;
struct EDGE{
int to,next;
}e[30005<<1|1];
inline void add_edge(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int now,int fa){
f[now]=fa;
s[now]++;
dep[now]=dep[fa]+1;
for(int i=head[now];i;i=e[i].next){
if(e[i].to==fa)
continue;
dfs1(e[i].to,now),s[now]+=s[e[i].to];
if(s[e[i].to]>s[son[now]])
son[now]=e[i].to;
}
}
void dfs2(int now,int t){
top[now]=t;
seg[id[now]=++cntseg]=now;
if(!son[now])
return;
dfs2(son[now],t);
for(int i=head[now];i;i=e[i].next)
if(e[i].to!=f[now]&&e[i].to!=son[now])
dfs2(e[i].to,e[i].to);
}
struct TREE{
int l,r,sum,maxn;
}t[30005<<2|1];
inline void pushup(int x){
t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
t[x].maxn=max(t[x<<1].maxn,t[x<<1|1].maxn);
}
void bt(int l,int r,int x){
t[x].l=l,t[x].r=r;
if(l==r){
t[x].sum=t[x].maxn=a[seg[l]];
return;
}
bt(l,(l+r)>>1,x<<1);
bt((l+r>>1)+1,r,x<<1|1);
pushup(x);
}
int qrysum(int l,int r,int x){
if(t[x].l>=l&&t[x].r<=r)
return t[x].sum;
int ans=0,mid=(t[x].l+t[x].r)>>1;
if(l<=mid)
ans+=qrysum(l,r,x<<1);
if(mid<r)
ans+=qrysum(l,r,x<<1|1);
return ans;
}
int qrymax(int l,int r,int x){
if(t[x].l>=l&&t[x].r<=r)
return t[x].maxn;
int ans=-1e9,mid=(t[x].l+t[x].r)>>1;
if(l<=mid)
ans=max(ans,qrymax(l,r,x<<1));
if(mid<r)
ans=max(ans,qrymax(l,r,x<<1|1));
return ans;
}
void upd(int p,int w,int x){
if(t[x].l==p&&p==t[x].r)
return (void)(t[x].sum=t[x].maxn=w);
int mid=(t[x].l+t[x].r)>>1;
if(p<=mid)
upd(p,w,x<<1);
else
upd(p,w,x<<1|1);
pushup(x);
}
int findmax(int x,int y){
if(top[x]==top[y])
return qrymax(dep[x]<dep[y]?id[x]:id[y],dep[x]>dep[y]?id[x]:id[y],1);
if(dep[top[x]]<dep[top[y]])
swap(x,y);
return max(qrymax(id[top[x]],id[x],1),findmax(f[top[x]],y));
}
int findsum(int x,int y){
if(top[x]==top[y])
return qrysum(dep[x]<dep[y]?id[x]:id[y],dep[x]>dep[y]?id[x]:id[y],1);
if(dep[top[x]]<dep[top[y]])
swap(x,y);
return qrysum(id[top[x]],id[x],1)+findsum(f[top[x]],y);
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++)
scanf("%d%d",&u,&v),add_edge(u,v),add_edge(v,u);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
scanf("%d",&q);
dep[0]=0;
dfs1(1,0);
dfs2(1,1);
bt(1,cntseg,1);
for(int i=1,u,v;i<=q;i++){
char s[15];
scanf("%s%d%d",s,&u,&v);
if(s[0]=='C')
upd(id[u],v,1);
else if(s[1]=='M')
printf("%d\n",findmax(u,v));
else
printf("%d\n",findsum(u,v));
}
return 0;
}
```
@[Steve_xh](/user/639198)
by __Aaaaaaaa @ 2023-12-22 16:20:56
@[Aaron_wch](/user/338880) 谢谢QwQ这些数据结构互套不是很熟练,谢谢指出
by Steve_xh @ 2023-12-22 16:24:40
%%% wtcl
by YC_George @ 2023-12-22 16:25:49