听说后天会考x

省选居然还考模板题的么（好吧好像NOI也有考而且也是树剖…）

题意：一棵树，每个点有权值，三种操作：单点修改、求链上最大值、求链上权值和。

直接上模板。

我可能不会写单点修改的线段树了就直接写了个区间修改的用…

#include
#include
#include
using namespace std;
const int N=30005;
const int T=233333;
inline int read()
{
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
return s*f;
}
struct edge
{
int to,nxt;
}edges[N<<1];
int n,q,cnt,tot;
int head[N<<1],trs[N<<2],trm[N<<2],lazy[N<<2],top[N],w[N],rk[N],fa[N],size[N],dep[N],son[N],idx[N];
char s[20];

inline void addEdge(int u,int v)
{
edges[++cnt]=(edge){v,head[u]};
head[u]=cnt;
}

#define lson (node<<1)
#define rson (node<<1|1)

inline void push_up(int node)
{
trs[node]=trs[lson]+trs[rson];
trm[node]=max(trm[lson],trm[rson]);
}
inline void push_down(int node,int l,int r)
{
if(lazy[node]==T)return;
int mid=(l+r)>>1;
trs[lson]=(mid-l+1)*lazy[node];trs[rson]=(r-mid)*lazy[node];trm[lson]=trm[rson]=lazy[node];
lazy[lson]=lazy[rson]=lazy[node];
lazy[node]=T;
}
inline void build(int node,int l,int r)
{
lazy[node]=T;
if(l==r)
{
trs[node]=trm[node]=w[rk[l]];
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
push_up(node);
}
inline void modify(int node,int l,int r,int ql,int qr,int val)
{
if(ql<=l&&r<=qr) { lazy[node]=val; trs[node]=(r-l+1)*val; trm[node]=val; return; } push_down(node,l,r);int mid=(l+r)>>1;
if(mid>=ql)modify(lson,l,mid,ql,qr,val);
if(mid+1<=qr)modify(rson,mid+1,r,ql,qr,val); push_up(node); } inline int query_max(int node,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr)return trm[node]; push_down(node,l,r);int mid=(l+r)>>1,res=-T;
if(mid>=ql)res=max(res,query_max(lson,l,mid,ql,qr));
if(mid+1<=qr)res=max(res,query_max(rson,mid+1,r,ql,qr)); return res; } inline int query_sum(int node,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr)return trs[node]; push_down(node,l,r);int mid=(l+r)>>1,res=0;
if(mid>=ql)res+=query_sum(lson,l,mid,ql,qr);
if(mid+1<=qr)res+=query_sum(rson,mid+1,r,ql,qr);
return res;
}

#undef lson
#undef rson

#define cur edges[i].to
inline void dfs1(int x)
{
size[x]=1;
for(register int i=head[x];i;i=edges[i].nxt)
if(cur!=fa[x])
{
fa[cur]=x;dep[cur]=dep[x]+1;
dfs1(cur);size[x]+=size[cur];
if(size[son[x]]<size[cur])son[x]=cur;
}
}
inline void dfs2(int x,int t)
{
idx[x]=++tot;top[x]=t;rk[tot]=x;
if(son[x])dfs2(son[x],t);
for(register int i=head[x];i;i=edges[i].nxt)
if(cur!=fa[x]&&cur!=son[x])dfs2(cur,cur);
}
#undef cur

inline int link_max(int a,int b)
{
int res=-T;
while(top[a]!=top[b])
{
if(dep[top[a]]dep[b])swap(a,b);
res=max(res,query_max(1,1,n,idx[a],idx[b]));
return res;
}
inline int link_sum(int a,int b)
{
int res=0;
while(top[a]!=top[b])
{
if(dep[top[a]]dep[b])swap(a,b);
res+=query_sum(1,1,n,idx[a],idx[b]);
return res;
}
int main()
{
n=read();
for(register int i=1;i<n;i++)
{
int u,v;u=read();v=read();
addEdge(u,v);addEdge(v,u);
}
for(register int i=1;i<=n;i++)w[i]=read();
dfs1(1);dfs2(1,1);build(1,1,n);
q=read();
for(register int i=1;i<=q;i++)
{
scanf("%s",s+1);
if(s[1]=='C')
{
int u,t;u=read();t=read();
modify(1,1,n,idx[u],idx[u],t);
}else
{
int u,v;u=read();v=read();
if(s[2]=='M')
printf("%d\n",link_max(u,v));
else
printf("%d\n",link_sum(u,v));
}
}
}