树链剖分之重链剖分
- 重儿子：儿子中最大size的节点
- 轻儿子：除重儿子外的儿子
- 重边：连接重儿子的边
- 轻边：连接轻儿子的边
- 重链：重儿子往上走到根节点或者轻儿子的边(亦可以是一个轻儿子)
对一棵树的路径进行大量的操作
树链剖分即将每条重链分出来 $ (O(logN)条) $
将节点按照先重儿子的dfs序排好,用线段树维护每个区间(重链)的信息
$ 总复杂度：O(log^2 N ) $
cpp
struct node{
ll l,r,add,sum;
} t[N<<2];
ll w[N],siz[N],id[N],nw[N],dep[N],top[N],par[N],son[N];
/*
w[i]是原来的值
siz[i]是树的大小
id[i]是dfs序编号
nw[i]是dfs序为i的值
dep[i]为高度
top[i]为当前i所在的重链的头部
par[i]为父节点
son[i]为重儿子
*/
ll n,m,r,mod;
vector<ll> adj[N];
void dfs1(int u,int fa){//预处理
par[u]=fa;
dep[u]=dep[fa]+1;
siz[u]=1;
for(auto v:adj[u]){
if(v==fa)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v])son[u]=v;
}
}
int cnt=0;
void dfs2(int u,int t){//dfs序，重链头节点
id[u]=++cnt;
nw[cnt]=w[u];
top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(auto v:adj[u]){
if(v==par[u]||v==son[u])continue;
dfs2(v,v);
}
}
void pushup(int p){
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void pushdown(int p){
auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
l.sum+=u.add*(l.r-l.l+1);
r.sum+=u.add*(r.r-r.l+1);
l.add+=u.add;
r.add+=u.add;
u.add=0;
}
void build(int p,int l,int r){
t[p]={l,r,0,nw[r]};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void modify(int p,int l,int r,int k){
if(l<=t[p].l&&r>=t[p].r){
t[p].add+=k;
t[p].sum+=k*(t[p].r-t[p].l+1);
return;
}
pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(l<=mid)modify(p<<1,l,r,k);
if(r>mid)modify(p<<1|1,l,r,k);
pushup(p);
}
ll query(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
pushdown(p);
ll res=0;
int mid=t[p].l+t[p].r>>1;
if(l<=mid)res+=query(p<<1,l,r);
if(r>mid)res+=query(p<<1|1,l,r);
return res;
}
void modify_path(int u,int v,int k){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
modify(1,id[top[u]],id[u],k);
u=par[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
modify(1,id[v],id[u],k);
}
ll query_path(int u,int v){
ll res=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
res+=query(1,id[top[u]],id[u]);
u=par[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
res+=query(1,id[v],id[u]);
return res;
}
void modify_tree(int u,int k){
modify(1,id[u],id[u]+siz[u]-1,k);
}
ll query_tree(int u){
return query(1,id[u],id[u]+siz[u]-1);
}
void solve(){
cin>>n>>m>>r>>mod;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
while(m--){
int op,x,y,z;
cin>>op>>x;
if(op==1){
cin>>y>>z;
modify_path(x,y,z);
}
else if(op==2){
cin>>y;
cout<<query_path(x,y)%mod<<"\n";
}
else if(op==3){
cin>>z;
modify_tree(x,z);
}
else{
cout<<query_tree(x)%mod<<"\n";
}
}
}