这就是个树剖板子。。。板子。。。板子。。。
维护一个sum，一个max，就好了。。。QAQ。。。
然而我数组开小。。。调了一天。。。艹
呆码：
#include<iostream> #include<cstdio> #define INF 99999999 #define maxn 100060 #define ll long long using namespace std; ll sum[maxn]; int num,head[maxn],siz[maxn],dep[maxn]; int id[maxn],cnt,wt[maxn],w[maxn],fa[maxn],n; int top[maxn],son[maxn],big[maxn]; char ch[11]; struct asd{ int nxt; int to; } a[maxn]; inline void add(int x,int y) { a[++num].nxt=head[x]; a[num].to=y; head[x]=num; } inline void dfs1(int x,int father,int deep) { dep[x]=deep; fa[x]=father; siz[x]=1; int maxson=-1; for(int i=head[x];i;i=a[i].nxt) { int to=a[i].to; if(to==father) continue; dfs1(to,x,deep+1); siz[x]+=siz[to]; if(siz[to]>maxson) { son[x]=to; maxson=siz[to]; } } } inline void dfs2(int x,int topp) { id[x]=++cnt; wt[cnt]=w[x]; top[x]=topp; if(!son[x]) return; dfs2(son[x],topp); for(int i=head[x];i;i=a[i].nxt) { if(a[i].to==fa[x] || a[i].to==son[x]) continue; dfs2(a[i].to,a[i].to); } } inline void pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; big[rt]=max(big[rt<<1],big[rt<<1|1]); } inline void build(int rt,int l,int r) { if(l==r) { sum[rt]=wt[l]; big[rt]=wt[l]; return; } int mid=l+r>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt); } inline void update(int rt,int l,int r,int L,int k) { int mid=l+r>>1; if(l==r) { sum[rt]=k; big[rt]=k; return;} if(L<=mid) update(rt<<1,l,mid,L,k); else update(rt<<1|1,mid+1,r,L,k); pushup(rt); } inline int queryx(int rt,int l,int r,int L,int R) { if(L<=l && r<=R) { return big[rt]; } int ans=-INF; int mid=l+r>>1; if(L<=mid) ans=max(ans,queryx(rt<<1,l,mid,L,R)); if(R>mid) ans=max(ans,queryx(rt<<1|1,mid+1,r,L,R)); pushup(rt); return ans; } inline int queryX(int x,int y) { int ans=-INF; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans=max(ans,queryx(1,1,n,id[top[x]],id[x])); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans=max(ans,queryx(1,1,n,id[x],id[y])); return ans; } inline ll querys(int rt,int l,int r,int L,int R) { if(L<=l && r<=R) { return sum[rt]; } int mid=l+r>>1; ll ans=0; if(L<=mid) ans+=querys(rt<<1,l,mid,L,R); if(R>mid) ans+=querys(rt<<1|1,mid+1,r,L,R); pushup(rt); return ans; } inline ll queryS(int x,int y) { ll ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=querys(1,1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans+=querys(1,1,n,id[x],id[y]); return ans; } int main() { scanf("%d",&n); int x,y; for(int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i=1;i<=n;i++) scanf("%d",&w[i]); dfs1(1,0,1); dfs2(1,1); build(1,1,n); int Q,u,v; scanf("%d",&Q); while(Q--) { scanf("%s%d%d",ch,&u,&v); if(ch[3]=='N') update(1,1,n,id[u],v); if(ch[3]=='X') printf("%d ",queryX(u,v)); if(ch[3]=='M') printf("%lld ",queryS(u,v)); } }