[luogu P2590 ZJOI2008] 樹的統計 (樹鏈剖分)

題目描述
一棵樹上有n個節點，編號分別為1到n，每個節點都有一個權值w。

我們將以下面的形式來要求你對這棵樹完成一些操作：

I. CHANGE u t : 把結點u的權值改為t

II. QMAX u v: 詢問從點u到點v的路徑上的節點的最大權值

III. QSUM u v: 詢問從點u到點v的路徑上的節點的權值和

注意：從點u到點v的路徑上的節點包括u和v本身

輸入輸出格式
輸入格式：
輸入文件的第一行為一個整數n，表示節點的個數。

接下來n – 1行，每行2個整數a和b，表示節點a和節點b之間有一條邊相連。

接下來一行n個整數，第i個整數wi表示節點i的權值。

接下來1行，為一個整數q，表示操作的總數。

接下來q行，每行一個操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式給出。

輸出格式：
對于每個“QMAX”或者“QSUM”的操作，每行輸出一個整數表示要求輸出的結果。

輸入輸出樣例
輸入樣例#1：
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
輸出樣例#1：
4
1
2
2
10
6
5
6
5
16
說明
對于100％的數據，保證1<=n<=30000，0<=q<=200000；中途操作中保證每個節點的權值w在-30000到30000之間。

樹鏈剖分模板。。。
code：

//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#define ll long long
#define f(a,b,c) for(int a=b;a<=c;a++)
using namespace std;inline ll rd() {ll x=0,fla=1; char c=' ';while(c>'9' || c<'0') {if(c=='-') fla=-fla; c=getchar();}while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*fla;
}inline void out(ll x){int a[25],wei=0;if(x<0) putchar('-'),x=-x;for(;x;x/=10) a[++wei]=x%10;if(wei==0){ puts("0"); return;}for(int j=wei;j>=1;--j) putchar('0'+a[j]);putchar('\n');
}const int MAX=300100;//直接開了十倍qwq
const int INF=0x3f3f3f3f;
int n,cnt,N;int head[MAX],W[MAX],size[MAX],h[MAX],fa[MAX],son[MAX];
//W 點權 size 樹的大小 h 深度 fa 父親 son 重兒子 int num[MAX],top[MAX],tree[MAX],maxn[MAX],sumn[MAX];
//num 在線段樹編號 top 鏈最上面的點 tree 線段樹編號對應的點 struct edges{int next,to;
}edge[MAX]; void add(int a,int b) {edge[++cnt]=(edges) {head[a],b}; head[a]=cnt;edge[++cnt]=(edges) {head[b],a}; head[b]=cnt;
}void dfs1(int u,int pre,int dep) {size[u]=1; h[u]=dep; fa[u]=pre;//initint mason=0;for(int i=head[u];i;i=edge[i].next) if(edge[i].to!=pre) {int v=edge[i].to;dfs1(v,u,dep+1);size[u]+=size[v];if(size[v]>mason) {mason=size[v];son[u]=v;}}
}void dfs2(int u,int pre) {if(son[pre]!=u) top[u]=u;else top[u]=top[pre];num[u]=++N;if(son[u]) dfs2(son[u],u);for(int i=head[u];i;i=edge[i].next)if(edge[i].to!=pre && edge[i].to !=son[u])dfs2(edge[i].to,u);
}void build_sum(int cur,int l,int r) {if(l==r) {sumn[cur]=W[tree[l]];return ;}int mid=(l+r)>>1;build_sum(cur<<1,l,mid);build_sum(cur<<1|1,mid+1,r);sumn[cur]=sumn[cur<<1]+sumn[cur<<1|1];//update_sum
}void build_max(int cur,int l,int r) {if(l==r) {maxn[cur]=W[tree[l]];return ;}int mid=(l+r)>>1;build_max(cur<<1,l,mid);build_max(cur<<1|1,mid+1,r);maxn[cur]=max(maxn[cur<<1],maxn[cur<<1|1]);//update_max
}void po_ch_sum(int cur,int l,int r,int x,int v) {//point_change_sumif(l==r) {sumn[cur]=v;return ;}int mid=(l+r)>>1;if(x<=mid) po_ch_sum(cur<<1,l,mid,x,v);else po_ch_sum(cur<<1|1,mid+1,r,x,v);sumn[cur]=sumn[cur<<1]+sumn[cur<<1|1];//update_sum
}void po_ch_max(int cur,int l,int r,int x,int v) {//point_change_maxif(l==r) {maxn[cur]=v;return ;}int mid=(l+r)>>1;if(x<=mid) po_ch_max(cur<<1,l,mid,x,v);else po_ch_max(cur<<1|1,mid+1,r,x,v);maxn[cur]=max(maxn[cur<<1],maxn[cur<<1|1]);
}int query_sum(int cur,int l,int r,int L,int R) {if(L<=l&&r<=R) return sumn[cur];int mid=(l+r)>>1,ans=0;if(L<=mid) ans+=query_sum(cur<<1,l,mid,L,R);if(R>mid) ans+=query_sum(cur<<1|1,mid+1,r,L,R);return ans;
}int query_max(int cur,int l,int r,int L,int R) {if(L<=l&&r<=R) return maxn[cur];int mid=(l+r)>>1,ans=-INF;if(L<=mid) ans=max(ans,query_max(cur<<1,l,mid,L,R));if(R>mid) ans=max(ans,query_max(cur<<1|1,mid+1,r,L,R));return ans;
}void INIT() {dfs1(1,0,1);// size h fa sondfs2(1,0);//top numf(i,1,n) tree[num[i]]=i;//tree//建樹： build_sum(1,1,N);build_max(1,1,N);
}void solve() {int q=rd(),a,b,ans=0,f1,f2;char opt[6];f(i,1,q) {scanf("%s",opt);a=rd(),b=rd(),ans=0;if(opt[0]=='C') {//HCANGEpo_ch_sum(1,1,N,num[a],b);po_ch_max(1,1,N,num[a],b);}else {f1=top[a],f2=top[b];if(opt[1]=='M') ans=-INF;while(f1!=f2) {if(h[f1]<h[f2]) {swap(a,b);swap(f1,f2);}if(opt[1]=='S') ans+=query_sum(1,1,N,num[f1],num[a]);else ans=max(ans,query_max(1,1,N,num[f1],num[a]));a=fa[f1];f1=top[a];}if(num[a]>num[b]) swap(a,b);if(opt[1]=='S') ans+=query_sum(1,1,N,num[a],num[b]);else ans=max(ans,query_max(1,1,N,num[a],num[b]));out(ans);}}
}int main() {n=rd();f(i,1,n-1) add(rd(),rd());f(i,1,n) W[i]=rd();INIT();solve();return 0;
}