接着找树剖的题。。。传送门（点我）
题意：给你一棵无根树，有三种操作：查询树上2点路径的点权和/最大点权；更改某点的点权。
解题思路：树链剖分裸题，我采用了常数较小的zkw线段树维护剖下来的树(毕竟线段树常数太大很危险），然后就是树剖的东西解决即可。
时间复杂度：期望：\( O(n \log \log^{2} n) \) 最坏：\( O(n \log^{2} n) \)
AC代码：（1452ms,3144KB on BZOJ)
#include <stdio.h>
#define inf 0x7fffffff
#define MN 30005
#define Mn 32768
#define v (edge[i].to)
inline int in(){
int x=,f=; char ch=getchar();
while(ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while(ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();
return x*f;
}inline int max(int a,int b){return a>b?a:b;}
struct zxy{int to,nxt;}edge[MN<<];
int top[MN],sum[Mn<<],ma[Mn<<],siz[MN],dep[MN],son[MN],fa[MN],pos[MN],head[MN],cnt,dfsn,n,q,M;
inline void ins(int x,int y){edge[++cnt].to=y,edge[cnt].nxt=head[x],head[x]=cnt;}
inline void dfs1(int u,int f,int d){
dep[u]=d,fa[u]=f,siz[u]=;
for (register int i=head[u]; i; i=edge[i].nxt)
if (v!=f){
dfs1(v,u,d+);siz[u]+=siz[v];
if (siz[v]>siz[son[u]]) son[u]=v;
}
}
inline void dfs2(int u,int tp){
pos[u]=(++dfsn);top[u]=tp;if (son[u]) dfs2(son[u],tp);
for (register int i=head[u]; i; i=edge[i].nxt)
if (v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
inline void combine(int x){sum[x]=sum[x<<]+sum[x<<|];ma[x]=max(ma[x<<],ma[x<<|]);}
inline void A(int x,int k){sum[x+=M]=k,ma[x]=k;for (x>>=; x; x>>=) combine(x);}
inline int QM(int l,int r){
register int res=-inf;
for (l+=M-,r+=M+; l^r^; l>>=,r>>=){
if (~l&) res=max(res,ma[l^]);
if (r&) res=max(res,ma[r^]);
}return res;
}
inline int QS(int l,int r){
register int res=;
for (l+=M-,r+=M+; l^r^; l>>=,r>>=){
if (~l&) res+=sum[l^];
if (r&) res+=sum[r^];
}return res;
}
inline int queryS(int x,int y){
register int res=;
while(top[x]!=top[y])
if (dep[top[x]]>dep[top[y]]) res+=QS(pos[top[x]],pos[x]),x=fa[top[x]];
else res+=QS(pos[top[y]],pos[y]),y=fa[top[y]];
if (dep[x]<dep[y]) res+=QS(pos[x],pos[y]);
else res+=QS(pos[y],pos[x]);return res;
}
inline int queryM(int x,int y){
register int res=-inf;
while(top[x]!=top[y])
if (dep[top[x]]>dep[top[y]]) res=max(res,QM(pos[top[x]],pos[x])),x=fa[top[x]];
else res=max(res,QM(pos[top[y]],pos[y])),y=fa[top[y]];
if (dep[x]<dep[y]) res=max(res,QM(pos[x],pos[y]));
else res=max(res,QM(pos[y],pos[x]));return res;
return res;
}
void init(){
n=in();for (int i=; i<n; ++i){
register int x=in(),y=in();
ins(x,y);ins(y,x);
}
dfs1(,,);dfs2(,);for (M=; M<n+; M<<=);
for (register int i=; i<=n; ++i)sum[M+pos[i]]=ma[M+pos[i]]=in();
for (register int i=M; i; --i) combine(i);
}
void solve(){
q=in();while(q--){
register char op[];scanf("%s",op);register int x=in();
if (op[]=='C') A(pos[x],in());
else{
if (op[]=='M') printf("%d\n",queryM(x,in()));
else printf("%d\n",queryS(x,in()));
}
}
}
int main(){init();solve();return ;}