听说后天会考x
省选居然还考模板题的么（好吧好像NOI也有考而且也是树剖…）
题意：一棵树，每个点有权值，三种操作：单点修改、求链上最大值、求链上权值和。
直接上模板。
我可能不会写单点修改的线段树了就直接写了个区间修改的用…
#include<cstdio> #include<cstring> #include<algorithm> 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[top[b]])swap(a,b); res=max(res,query_max(1,1,n,idx[top[a]],idx[a])); a=fa[top[a]]; } if(dep[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[top[b]])swap(a,b); res+=query_sum(1,1,n,idx[top[a]],idx[a]); a=fa[top[a]]; } if(dep[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 ",link_max(u,v)); else printf("%d ",link_sum(u,v)); } } }