son[x]
表示节点\(x\)的重儿子,若为\(0\),则说明\(x\)为叶子节点
id[x]
表示节点\(x\)的dfs序编号
f[x]
表示节点\(x\)的父节点
dep[x]
表示节点\(x\)的深度
sz[x]
表示节点为\(x\)的子树的大小
top[x]
表示x所在重链顶部的节点
函数原型void dfs1(ll u,ll fa)
功能:计算dep[]
、f[]
、sz[]
和son[]
。
函数原型void dfs2(ll u,ll topu)
功能:计算id[]
、top[]
和线段树每个位置的初始值。
函数原型void update_range(ll x,ll y,ll k)
功能:
函数原型ll query_range(ll x,ll y)
功能:
函数原型void update_tree(ll x,ll k)
功能:
函数原型ll query_tree(ll x)
功能:
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll n,m,r,mod,w[N],a[N];
vector<ll> G[N];
ll dat[N<<2],lazy[N<<2];
ll son[N],id[N],f[N],dep[N],sz[N],top[N],tot;
void down(ll p,ll l,ll r){
if(lazy[p]==0||l==r)return;
lazy[p<<1]+=lazy[p],lazy[p<<1]%=mod;
dat[p<<1]+=(mid-l+1)*lazy[p],dat[p<<1]%=mod;
lazy[(p<<1)|1]+=lazy[p],lazy[(p<<1)|1]%=mod;
dat[(p<<1)|1]+=(r-mid)*lazy[p],dat[(p<<1)|1]%=mod;
lazy[p]=0;
}
void update(ll p,ll l,ll r,ll L,ll R,ll k){
if(L<=l&&r<=R){
dat[p]+=(r-l+1)*k,dat[p]%=mod;
lazy[p]+=k,lazy[p]%=mod;
return;
}
down(p,l,r);
if(L<=mid)update(p<<1,l,mid,L,R,k);
if(mid+1<=R)update((p<<1)|1,mid+1,r,L,R,k);
dat[p]=dat[p<<1]+dat[(p<<1)|1],dat[p]%=mod;
}
ll query(ll p,ll l,ll r,ll L,ll R){
if(L<=l&&r<=R)return dat[p];
down(p,l,r);
ll ret=0;
if(L<=mid)ret+=query(p<<1,l,mid,L,R),ret%=mod;
if(mid+1<=R)ret+=query((p<<1)|1,mid+1,r,L,R),ret%=mod;
return ret;
}
void build(ll p,ll l,ll r){
if(l==r){
dat[p]=a[l];
return;
}
build(p<<1,l,mid);
build((p<<1)|1,mid+1,r);
dat[p]=dat[p<<1]+dat[(p<<1)|1];
}
void dfs1(ll u,ll fa){
dep[u]=dep[fa]+1,f[u]=fa,sz[u]=1;
for(ll i=0;i<G[u].size();i++){
ll v=G[u][i];
if(v==fa)continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v])son[u]=v;
}
}
void dfs2(ll u,ll topu){
a[id[u]=++tot]=w[u],top[u]=topu;
if(!son[u])return;
dfs2(son[u],topu);
for(ll i=0;i<G[u].size();i++){
ll v=G[u][i];
if(v==f[u]||v==son[u])continue;
dfs2(v,v);
}
}
void update_range(ll x,ll y,ll k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,id[top[x]],id[x],k);
x=f[top[x]];
}
update(1,1,n,min(id[x],id[y]),max(id[x],id[y]),k);
}
ll query_range(ll x,ll y){
ll ret=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ret+=query(1,1,n,id[top[x]],id[x]),ret%=mod;
x=f[top[x]];
}
ret+=query(1,1,n,min(id[x],id[y]),max(id[x],id[y])),ret%=mod;
return ret;
}
void update_tree(ll x,ll k){
update(1,1,n,id[x],id[x]+sz[x]-1,k);
}
ll query_tree(ll x){
return query(1,1,n,id[x],id[x]+sz[x]-1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m >> r >> mod;
for(ll i=1;i<=n;i++)cin >> w[i],w[i]%=mod;
for(ll i=1;i<=n-1;i++){
ll u,v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
while(m--){
ll op,x,y,z;
cin >> op >> x;
if(op==1){
cin >> y >> z;
update_range(x,y,z);
}else if(op==2){
cin >> y;
cout << query_range(x,y) << endl;
}else if(op==3){
cin >> z;
update_tree(x,z);
}else if(op==4){
cout << query_tree(x) << endl;
}
}
return 0;
}
标签:剖分,ll,update,树链,原型,void,节点,op
From: https://www.cnblogs.com/ningziang/p/17947626