Top Cluster树分块-树剖模板
读了集训队论文周 欣 - 《浅谈一类树分块的构建算法及其应用》，然后按照自己理解实现了个巨大麻烦的写法，轻喷/kel。
支持树链加链求和子树加子树求和。
一些扩展暂时无限期咕咕咕，省选不退役再更新。
真正的树分块
const int N=2e5+5,M=1e6+5,INF=1e9+7,NB=1e5+5,B=317;
int n,m,r,a[N],val[N],head[N],idx;
struct node{int nex,to;}e[N<<1];
void add(int u,int v){e[++idx].nex=head[u];e[idx].to=v;head[u]=idx;return ;}
int top[N],dep[N],siz[N],son[N];
int fa[N];
int nnum,num[NB],Len[NB],bel[N];
int sum1[NB],sum2[NB],tg1[NB],tg2[NB];
int st[N],st_cnt;
//当前簇对应的点集，不包含上界点，加入时按照 DFS 序排序
int ner[N],up[N],dw[N];
//当前点最近的簇路径上点，当前点簇的上下界点
vector<int>G[N];
void ad(int x,int v){
val[x]+=v;
if(x!=up[x]&&x!=dw[x]){
sum2[bel[x]]+=v;
if(x==ner[x]) sum1[bel[x]]+=v;
}
return ;
}
void AddCluster(int u,int v){//建立树簇(u,v)，且u是v的祖先
nnum++;
ner[u]=u;
if(!v) v=st[st_cnt];//若没有下界点
G[u].pb(v);//虚树
for(int x=v;x!=u;x=fa[x]) ner[x]=x;
for(int i=1;i<=st_cnt;i++){
const int &x=st[i];
up[x]=u,dw[x]=v;
bel[x]=nnum;
if(!ner[x]){
int w=x;
while(!ner[w]) w=fa[w];
ner[x]=ner[w];
}
ad(x,a[x]);
}
num[nnum]=st_cnt-1;
Len[nnum]=dep[v]-dep[u]-1;
st_cnt=0;
return ;
}
// s / s_cnt: 维护未归类点的栈
// los / vid: Dfs 之后未归类点的个数 / 应当作为下界点的编号
// inid: 进入点 u 时的 s_cnt
int s[N],s_cnt,inid[N],los[N],vid[N];
void Dfs(int x,int f){//Top Cluster分解
dep[x]=dep[f]+1;siz[x]=1;
fa[x]=f;inid[x]=s_cnt;los[x]=1;
int v_num=0;
for(int i=head[x];i;i=e[i].nex){
int y=e[i].to;
if(y==f) continue;
s[++s_cnt]=y;
Dfs(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
los[x]+=los[y];
if(vid[y]) vid[x]=vid[y],v_num++;
}
if(los[x]>B||v_num>1||!f){
vid[x]=x;los[x]=0;
int nlos=0,nvid=0,pos=inid[x]+1;
for(int i=head[x];i;i=e[i].nex){
int y=e[i].to;
if(y==f) continue;
if(nlos+los[y]>B||(nvid&&vid[y])){
while(pos<inid[y]&&pos<=s_cnt) st[++st_cnt]=s[pos],pos++;
AddCluster(x,nvid);
nvid=nlos=0;
}
nlos+=los[y];
if(vid[y]) nvid=vid[y];
}
while(pos<=s_cnt) st[++st_cnt]=s[pos++];
AddCluster(x,nvid);
s_cnt=inid[x];
}
return ;
}
void dfs1(int x,int f){//树剖求lca用
if(x==son[f]) top[x]=top[f];
else top[x]=x;
if(son[x]) dfs1(son[x],x);
for(int i=head[x];i;i=e[i].nex){
int y=e[i].to;
if(y==f||y==son[x]) continue;
dfs1(y,x);
}
return ;
}
int LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
void ModifyRoad1(int x,int y,int v1){//修改(x,y)链（不包含y）
int u=up[x],v=dw[y];
if(bel[x]==bel[y]){//同一个簇内
while(x!=y) ad(x,v1),x=fa[x];
return ;
}
while(x!=u) ad(x,v1),x=fa[x];
while(x!=v){
const int &tmp=bel[x];
ad(x,v1);
sum1[tmp]+=Len[tmp]*v1,
sum2[tmp]+=Len[tmp]*v1,
tg1[tmp]+=v1,
x=up[x];
}
while(x!=y) ad(x,v1),x=fa[x];
return ;
}
void ModifyRoad(int x,int y,int v){//链加 (x,y)
int lca=LCA(x,y);
ModifyRoad1(x,lca,v);
ModifyRoad1(y,lca,v);
ad(lca,v);
return ;
}
void Change(int x,int f,int v,int id){//更改子树当前簇内信息
ad(x,v);
for(int i=head[x];i;i=e[i].nex){
int y=e[i].to;
if(y==f||y==id) continue;
Change(y,x,v,id);
}
return ;
}
void Change1(int x,int v){
val[x]+=v;//界点修改
for(int y:G[x]){
const int &tmp=bel[y];
sum1[tmp]+=v*Len[tmp];
sum2[tmp]+=v*num[tmp];
tg2[tmp]+=v;
Change1(y,v);
}
return ;
}
void ModifyTree(int x,int v){
if(x!=dw[x]&&x!=up[x]) Change(x,fa[x],v,dw[x]);
int lca=LCA(x,dw[x]);
if(lca!=x) return ;
Change1(dw[x],v);
return ;
}
int As(int x){
int res=val[x];
if(x!=up[x]&&x!=dw[x]){
res+=tg2[bel[x]];
if(x==ner[x]) res+=tg1[bel[x]];
}
return res;
}
int QueryRoad1(int x,int y){//查询(x,y)链（不包含y）
int u=up[x],v=dw[y];
int res=0;
if(bel[x]==bel[y]){//同一个簇内
while(x!=y) res+=As(x),x=fa[x];
return res;
}
while(x!=u) res+=As(x),x=fa[x];
while(x!=v){
const int &tmp=bel[x];
res+=As(x);
res+=sum1[tmp];
x=up[x];
}
while(x!=y) res+=As(x),x=fa[x];
return res;
}
int QueryRoad(int x,int y){//修改路径
int lca=LCA(x,y);
int res=0;
res=QueryRoad1(x,lca);
res+=QueryRoad1(y,lca);
return res+As(lca);
}
int Query1(int x,int f,int id){//查询除开界点的子树
int res=As(x);
for(int i=head[x];i;i=e[i].nex){
int y=e[i].to;
if(y==f||y==id) continue;
res+=Query1(y,x,id);
}
return res;
}
int Query(int x){//查询界点子树
int res=val[x];
for(int y:G[x]){
const int &tmp=bel[y];
res+=sum2[tmp];
res+=Query(y);
}
return res;
}
int QueryTree(int x){//子树查询
int res=0;
if(x!=dw[x]&&x!=up[x]) res+=Query1(x,fa[x],dw[x]);
int lca=LCA(x,dw[x]);
if(lca!=x) return res;
res+=Query(dw[x]);
return res;
}
inline void _Solve(){
read(n,m,r,MOD);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<n;i++){
int u,v;
read(u,v);
add(u,v),add(v,u);
}
Dfs(r,0);
up[r]=dw[r]=ner[r]=r;
val[r]=a[r];//需要特判根节点所在块
dfs1(r,0);
while(m--){
int op,x,y,v;
read(op);
if(op==1){
read(x,y,v);
ModifyRoad(x,y,v);
}
else if(op==2){
read(x,y);
write(QueryRoad(x,y)),pc('\n');
}
else if(op==3){
read(x,v);
ModifyTree(x,v);
}
else{
read(x);
write(QueryTree(x)),pc('\n');
}
}
return ;
}
/*
*/