代码有点多余的没删干净
这个能过编译
```cpp
#include<bits/stdc++.h>
#define N 100005
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
inline long long read(){
long long tmp=0;
short f=1;
char a=getchar();
while(a<'0' || a>'9'){
if(a=='-')f=-f;
a=getchar();
}
while(a>='0' and a<='9'){
tmp=(tmp<<1)+(tmp<<3)+a-'0';
a=getchar();
}
return tmp*f;
}
inline void write(long long x){
long long y=x,cnt=0;char tmp[1005];
if(y<0)putchar('-'),y=-y;
while(y)cnt++,tmp[cnt]=y%10+'0',y/=10;
while(cnt)putchar(tmp[cnt]),cnt--;
putchar('\n');
}
int n,m;
struct ANS{
long long s,mx;
ANS operator +(const ANS &x)const{
return {s+x.s,max(mx,x.mx)};
}
};
struct TREE{
int a[N];//原点权数组
vector<int>G[N];//建图
int fa[N],dep[N],siz[N],top[N],son[N];//父亲，深度，树的大小，重儿子
int seg[N];//线段树编号
long long s[N<<2],mx[N<<2];
inline void init(){
cin >> n;
for(int i=1;i<=n-1;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];
}
inline void dfs1(int u,int ff){
siz[u]=1,fa[u]=ff,dep[u]=dep[ff]+1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==ff)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
inline void dfs2(int u){
if(son[u]){
seg[son[u]]=++seg[0],top[son[u]]=top[u];
dfs2(son[u]);
}
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(top[v] or v==son[u])continue;
seg[v]=++seg[0];
top[v]=v;
dfs2(v);
}
}
inline void pushup(int p){//合并信息
s[p]=s[ls(p)]+s[rs(p)],mx[p]=max(mx[ls(p)],mx[rs(p)]);
}
inline void build(int p,int l,int r){//建树
if(l==r){
mx[p]=s[p]=a[seg[l]];
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pushup(p);
}
inline void update(int p,int l,int r,int k,int x){//单点修改
if(l>k or r<k)return;
if(l==r){
s[p]=mx[p]=x;
return;
}
int mid=(l+r)>>1;
update(ls(p),l,mid,k,x);
update(rs(p),mid+1,r,k,x);
pushup(p);
}
inline ANS query(int p,int l,int r,int L,int R){//线段树上查询
if(r<L or l>R)return (ANS){0,-1e9};
if(L<=l and r<=R)return {s[p],mx[p]};
int mid=(l+r)>>1;
ANS tmp=query(ls(p),l,mid,L,R)+query(rs(p),mid+1,r,L,R);
pushup(p);
return tmp;
}
inline ANS ask(int x,int y){//询问
int fx=top[x],fy=top[y];
ANS tmp={0,-1e9};
while(fx!=fy){
if(dep[fx]<dep[fy]){swap(x,y),swap(fx,fy);}
tmp=tmp+query(1,1,seg[0],seg[fx],seg[x]);
x=fa[fx],fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
return tmp+query(1,1,seg[0],seg[x],seg[y]);
}
}T;
signed main(){
T.init();
T.dfs1(1,0);
T.seg[0]=T.seg[1]=T.top[1]=1;//初始化树根
T.dfs2(1);
T.build(1,1,T.seg[0]);
cin >> m;
while(m--){
char opt[105];
scanf("%s",opt);
int x,y;
cin >> x >> y;
if(opt[0]=='C')T.update(1,1,T.seg[0],T.seg[x],y);//单点修改
else{
ANS tmp=T.ask(x,y);
cout << (opt[1]=='M'?tmp.mx:tmp.s) << endl;
}
}
return 0;
}
```
by D4C_LoveTrain @ 2024-02-18 09:37:04