```cpp
#include<bits/stdc++.h>
using namespace std;
inline
int getint(){
int num=0,c;
bool f=0;
while(!isdigit(c=getchar()))if(c=='-')break;
if(c=='-')f=1,c=getchar();
while(isdigit(c))num=(num<<1)+(num<<3)+c-'0',c=getchar();
return f?-num:num;
}
inline
void outint(int x){
if(x<0)return(void)(putchar('-'),outint(-x));
if(x>9)outint(x/10);
putchar(x%10+'0');
}
inline
void swap(int &x,int &y){
x^=y;
y^=x;
x^=y;
}
int n;
int Last[30005],to[60005],nxt[60005],ecnt=0;
inline
void addedge(int u,int v){
nxt[++ecnt]=Last[u],Last[u]=ecnt,to[ecnt]=v;
nxt[++ecnt]=Last[v],Last[v]=ecnt,to[ecnt]=u;
}
int val[30005],id[30005],pos[30005],fa[30005],siz[30005],top[30005],dep[30005],son[30005],tot;
int sum[120005],maxn[120005];
inline
void dfs1(int u){
siz[u]=1;
for(int v,e=Last[u];e;e=nxt[e]){
if((v=to[e])==fa[u])continue;
fa[v]=u;
dep[v]=dep[u]+1;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
inline
void dfs2(int u){
if(son[u]){
id[pos[son[u]]=++tot]=son[u];
top[son[u]]=top[u];
dfs2(son[u]);
}
for(int v,e=Last[u];e;e=nxt[e]){
if((v=to[e])==fa[u]||v==son[u])continue;
id[pos[v]=++tot]=v;
top[v]=v;
dfs2(v);
}
}
inline
void init(){
dfs1(1);
top[1]=id[1]=pos[1]=tot=1;
dfs2(1);
}
inline
void build(int k,int l,int r){
if(l==r){
sum[k]=maxn[k]=val[id[l]];
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}
inline
void modify(int k,int l,int r,int p,int v){
if(l==r)return (void)(sum[k]=maxn[k]=val[id[l]]=v);
int mid=(l+r)>>1;
if(p<=mid)modify(k<<1,l,mid,p,v);
else modify(k<<1|1,mid+1,r,p,v);
sum[k]=sum[k<<1]+sum[k<<1|1];
maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}
inline
int querysum(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return sum[k];
int mid=(l+r)>>1,ans=0;
if(x<=mid)ans+=querysum(k<<1,l,mid,x,y);
if(y>=mid+1)ans+=querysum(k<<1|1,mid+1,r,x,y);
return ans;
}
inline
int querymax(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return maxn[k];
int mid=(l+r)>>1,ans=-30005;
if(x<=mid)ans=max(ans,querymax(k<<1,l,mid,x,y));
if(mid<y)ans=max(ans,querymax(k<<1|1,mid+1,r,x,y));
return ans;
}
inline
int pathsum(int v,int u){
if(top[v]!=top[u]){
if(dep[top[v]]>dep[top[u]])swap(v,u);
return pathsum(fa[top[u]],v)+querysum(1,1,n,pos[top[u]],pos[u]);
}
if(dep[u]>dep[v])swap(u,v);
return querysum(1,1,n,pos[u],pos[v]);
}
inline
int pathmax(int v,int u){
if(top[v]!=top[u]){
if(dep[top[v]]>dep[top[u]])swap(v,u);
return max(pathmax(fa[top[u]],v),querymax(1,1,n,pos[top[u]],pos[u]));
}
if(dep[u]>dep[v])swap(u,v);
return querymax(1,1,n,pos[u],pos[v]);
}
char op;
int q;
int main(){
n=getint();
for(int i=1;i<n;++i)addedge(getint(),getint());
for(int i=1;i<=n;++i)val[i]=getint();
init();
build(1,1,n);
/* for(int i=1;i<=n;++i)outint(val[i]),putchar(' ');puts("");
for(int i=1;i<=n;++i)outint(id[i]),putchar(' ');puts("");
for(int i=1;i<=n;++i)outint(pos[i]),putchar(' ');puts("");
for(int i=1;i<=n<<2;++i)outint(sum[i]),putchar(' ');puts("");
for(int i=1;i<=n<<2;++i)outint(maxn[i]),putchar(' ');puts("");*/
q=getint();
while(q--){
while((op=getchar())!='Q'&&op!='C');
if('Q'==op)op=getchar();
int u=getint();
int v=getint();
switch(op){
case 'M':outint(pathmax(u,v));putchar('\n');break;
case 'S':outint(pathsum(u,v));putchar('\n');break;
case 'C':
modify(1,1,n,pos[u],v);
//for(int i=1;i<=n<<2;++i)outint(sum[i]),putchar(' ');puts("");
//for(int i=1;i<=n<<2;++i)outint(maxn[i]),putchar(' ');puts("");
break;
default :break;
}
}
return 0;
}
```
by _meaningless_ @ 2018-06-25 13:44:18
唯一区别在main里面
by _meaningless_ @ 2018-06-25 13:45:02
```cpp
#include<bits/stdc++.h>
using namespace std;
inline
int getint(){
int num=0,c;
bool f=0;
while(!isdigit(c=getchar()))if(c=='-')break;
if(c=='-')f=1,c=getchar();
while(isdigit(c))num=(num<<1)+(num<<3)+c-'0',c=getchar();
return f?-num:num;
}
inline
void outint(int x){
if(x<0)return(void)(putchar('-'),outint(-x));
if(x>9)outint(x/10);
putchar(x%10+'0');
}
inline
void swap(int &x,int &y){
x^=y;
y^=x;
x^=y;
}
int n;
int Last[30005],to[60005],nxt[60005],ecnt=0;
inline
void addedge(int u,int v){
nxt[++ecnt]=Last[u],Last[u]=ecnt,to[ecnt]=v;
nxt[++ecnt]=Last[v],Last[v]=ecnt,to[ecnt]=u;
}
int val[30005],id[30005],pos[30005],fa[30005],siz[30005],top[30005],dep[30005],son[30005],tot;
int sum[120005],maxn[120005];
inline
void dfs1(int u){
siz[u]=1;
for(int v,e=Last[u];e;e=nxt[e]){
if((v=to[e])==fa[u])continue;
fa[v]=u;
dep[v]=dep[u]+1;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
inline
void dfs2(int u){
if(son[u]){
id[pos[son[u]]=++tot]=son[u];
top[son[u]]=top[u];
dfs2(son[u]);
}
for(int v,e=Last[u];e;e=nxt[e]){
if((v=to[e])==fa[u]||v==son[u])continue;
id[pos[v]=++tot]=v;
top[v]=v;
dfs2(v);
}
}
inline
void init(){
dfs1(1);
top[1]=id[1]=pos[1]=tot=1;
dfs2(1);
}
inline
void build(int k,int l,int r){
if(l==r){
sum[k]=maxn[k]=val[id[l]];
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}
inline
void modify(int k,int l,int r,int p,int v){
if(l==r)return (void)(sum[k]=maxn[k]=val[id[l]]=v);
int mid=(l+r)>>1;
if(p<=mid)modify(k<<1,l,mid,p,v);
else modify(k<<1|1,mid+1,r,p,v);
sum[k]=sum[k<<1]+sum[k<<1|1];
maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}
inline
int querysum(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return sum[k];
int mid=(l+r)>>1,ans=0;
if(x<=mid)ans+=querysum(k<<1,l,mid,x,y);
if(y>=mid+1)ans+=querysum(k<<1|1,mid+1,r,x,y);
return ans;
}
inline
int querymax(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return maxn[k];
int mid=(l+r)>>1,ans=-30005;
if(x<=mid)ans=max(ans,querymax(k<<1,l,mid,x,y));
if(mid<y)ans=max(ans,querymax(k<<1|1,mid+1,r,x,y));
return ans;
}
inline
int pathsum(int v,int u){
if(top[v]!=top[u]){
if(dep[top[v]]>dep[top[u]])swap(v,u);
return pathsum(fa[top[u]],v)+querysum(1,1,n,pos[top[u]],pos[u]);
}
if(dep[u]>dep[v])swap(u,v);
return querysum(1,1,n,pos[u],pos[v]);
}
inline
int pathmax(int v,int u){
if(top[v]!=top[u]){
if(dep[top[v]]>dep[top[u]])swap(v,u);
return max(pathmax(fa[top[u]],v),querymax(1,1,n,pos[top[u]],pos[u]));
}
if(dep[u]>dep[v])swap(u,v);
return querymax(1,1,n,pos[u],pos[v]);
}
char op;
int q;
int main(){
n=getint();
for(int i=1;i<n;++i)addedge(getint(),getint());
for(int i=1;i<=n;++i)val[i]=getint();
init();
build(1,1,n);
q=getint();
while(q--){
while((op=getchar())!='Q'&&op!='C');
if('Q'==op)op=getchar();
switch(op){
case 'M':outint(pathmax(getint(),getint()));putchar('\n');break;
case 'S':outint(pathsum(getint(),getint()));putchar('\n');break;
case 'C':
modify(1,1,n,pos[getint()],getint());
break;
default :break;
}
}
return 0;
}
```
by _meaningless_ @ 2018-06-25 13:45:32