轉自這位大神

DFS序分塊

將樹節點按照DFS序每sqrtnsqrtn個分成一塊，可以處理關于子樹問題
但是由于在DFS序上分塊基本都可以用logn的數據結構代替，所以很不常用

這種分塊方式保證塊的大小和數量，不保證塊的連通和直徑

Size分塊

對于一個節點，如果它的父親所屬塊的大小小于sqrtnsqrtn，則將該點加入其父親的塊?
否則新建一個塊，將該點加入新的塊中

這種分塊方式保證塊的大小、直徑，不保證塊的數量

例題?BZOJ3720: Gty的妹子樹

王室聯邦分塊

分塊的名稱來自BZOJ?1086: [SCOI2005]王室聯邦

具體做法：

首先從根dfs整棵樹，如果某棵子樹剩余大小大于B，就將它單獨成一塊，并將它移除(即不再記錄它的大小)
如果最后樹的節點個數不足B，就把它加入上一塊。z

這樣分塊每塊大小為[B,3B)(只有一塊，剩下的塊直徑不超過2B),直徑不超過3B、但不保證連通。可以在樹上莫隊中使用

#include<cstdio> #define maxn 1005 struct Edge{int next,to; }edge[maxn*2]; int fi[maxn],se,n,b,stack[maxn],t,belong[maxn],size,head[maxn]; inline void add_edge(int u,int v){edge[++se].next=fi[u],edge[se].to=v,fi[u]=se,edge[++se].next=fi[v],edge[se].to=u,fi[v]=se; } void out(int s){size++;while(t>s)belong[stack[--t]]=size; } void dfs(int x,int s,int fa){for(int i=fi[x];i;i=edge[i].next){int v=edge[i].to;if(v==fa)continue;dfs(v,t,x); if(t-s>=b)out(s),head[size]=x;//如果當前子樹棧中節點>=B,就自成一塊 }stack[t++]=x; } int main(){scanf("%d%d",&n,&b);int u,v;for(int i=1;i<n;i++)scanf("%d%d",&u,&v),add_edge(u,v);dfs(1,0,0);while(t)belong[stack[--t]]=size;//將最后剩下的節點加入最后一個塊 printf("%d\n",size);for(int i=1;i<=n;i++)printf("%d ",belong[i]);printf("\n");for(int i=1;i<=size;i++)printf("%d ",head[i]);return 0; }

深度分塊

設size=n??√size=n,對于每個節點x，如果depth[x]%size==1depth[x]%size==1則稱它是關鍵點。
于是這棵樹就被這些關鍵點分成了若干塊(關鍵點屬于它下面的塊)，如果某一塊的大小小于size，就把它和上一個塊合并。
這棵樹的每個塊大小就≥size≥size,塊的個數就≤size≤size,并且每個塊的直徑≤size?4≤size?4

這種分塊方式可以保證塊的個數、塊的直徑，但不能保證塊的大小，用于解決對樹上的鏈進行詢問

int dfs(int x){//深度分塊 int si=1;stack[top++]=x;//將x加入棧中 for(int i=fi[x];i;i=edge[i].next){int v=edge[i].to;if(v==fa[x])continue;dis[v]=edge[i].w,fa[v]=x,depth[v]=depth[x]+1,si+=dfs(v);}int k; if(depth[x]%size==0&&si>=size){//如果當前點深度%size==0且子樹大小>=size，則要和它的父親分開 k=++s;block[x]=k;key[k]=x;//棧中x的子樹中的節點和x一個塊 while(stack[--top]!=x){block[stack[top]]=k;}}//否則和它的父親一個塊 return si; }

例題?CodeChef TRIPS-Children Trips 樹上分塊， bzoj3351

保留塊之間祖先關系的深度分塊

設size=n??√size=n,對于每個節點x，如果depth[x]depth[x]則稱它是關鍵點。
對于任意兩個關鍵點的最近公共祖先也設成關鍵點，可證明新加關鍵點數不會超過原關鍵點數。
將這些關鍵點建成一棵虛樹，虛樹上每個節點是一個塊。
這些關鍵點之間的路徑上的點都屬于靠下的關鍵點所在的塊
不在路徑上的點都加入到最近的關鍵點(一定是自己的祖先)(與路徑上的點分開保存)。
可證明每個塊中路徑上的點都是它子樹的塊中所有節點(在和不在路徑上的點)和它自己塊中不在路徑上的點的祖先

這種分塊可以保證塊的直徑和個數，不保證塊的大小，可以解決以祖先關系為基礎的詢問?

int dfs(int x,int depth){int si=1,ma=0;//ma記錄他有幾個兒子的子樹有關鍵點 for(int i=fi[x];i;i=edge[i].next){int v=edge[i].to;fa[v]=x,si+=dfs(v,depth+1);if(k[v])ma++;//k==1表示v子樹中存在關鍵點 }if((depth%size==0&&si>=size)||ma>1){ k[x]=key[x]=1;//如果它本身是關鍵點 或 有2個及以上的兒子的子樹有關鍵點，則它是關鍵點 }else if(ma)k[x]=1;//它的子樹有關鍵點return si; } void dfs1(int x){if(key[x])block[x]=++s;for(int i=fi[x];i;i=edge[i].next){dfs1(edge[i].to);}int v=x;if(key[x]){v=x;while(!key[fa[v]])v=fa[v],block[v]=block[x];//將路徑上的點加入當前塊 v=fa[v];add_road(block[v],block[x]);//構建虛樹中的邊 }else if(!block[x]){while(!key[fa[v]])v=fa[v];v=fa[v],block[x]=-block[v];//不在路徑上的點屬于它最近關鍵點所在塊(分開保存，所以存成負數)} }

轉載于:https://www.cnblogs.com/ZJXXCN/p/10713996.html

總結

以上是生活随笔為你收集整理的树上分块初步的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。