我们有对序列分块的需求。所以我们有对树分块的需求。
有些出题人喜欢把序列问题放到树上，从而让选手强行写树链剖分。
但是我们想让大家知道，搬到仙人掌上也是可以的。
先给出一些信息：
-
一个树簇 (cluster) 是树上的一个连通子图，有至多两个点和全树的其他位置连接。
-
这两个节点被称为界点，可以证明，两个界点存在祖孙关系，我们定义深度小的为上界点，另一个为下界点。
-
不同块的边集不交，一个界点可能在多个簇里面，非界点只可能在一个块里。
-
两个界点之间的路径被称为簇路径。
-
如果一个点在多个块里，那一定是一个簇的下界点，同时可能作为很多个簇的上界点。
-
如果把所有块的端点作为点，每个簇的上界点和下界点连边，则得到一棵树，称为收缩树。
根据这些性质，类似于树剖维护边，我们把每个簇的信息记录在下界点上。
对于根，一般特殊维护，不进行任何关于根的修改、查询。
我们考虑如何构建树分块。
我们从根开始 dfs，我们定义一个栈维护还未被划分到哪个簇的边，在三种情况下需要把边弹出来。
-
x 为根，为了方便以后的处理，强行钦定 x 为界点。
-
当前子树中出现了两个界点，我们必须令这个点为界点来隔开两个簇。
-
栈中的边的数量大于了 B。
为什么？1、3 显然。对于 2，我们不希望一个簇有两个下界点，然而子树中的上界点如果作为子树那个簇独立就必须成为当前节点的下界点。但是这不可能。所以我们要合并这两个子树，并以当前的节点作为簇的上界点。
可以证明，这样的簇至多有 \(\dfrac{6n}{B}\) 个。很好！
那么如何利用它呢？这里以常用的链修改、查询为例。
记录块内的簇路径前缀和、收缩树前缀和，每个点到其簇上界点的前缀和。
先把链拆分成祖先-后代链。
修改：对于 \(x\) 所在簇暴力修改，然后对其他块都是簇路径，打标记即可。
查询利用几个前缀和即可。
复杂度是优秀的 \(O(\sqrt n)-O(1)\)。
口胡容易实现代码难。我们来看有详细注释的代码：
这里使用 P4211 的代码。其要求链修链查。但是转化问题不在这里提及，这里着重看树分块。
数组意义：
dep 原树深度，f 原树父亲，Fa 收缩树父亲，sz 子树中未分配点个数，up/down 这个点所属簇的上下界。
uper/downer 这个编号的簇的上下界，stk 是目前（dfs中）的这个簇的元素集合，top 是他的栈顶。
cnt 是簇数量，near 是这个点离簇路径最近的那个点，ind 一个点属于那个块，st 是目前的节点栈，Top 是他的栈顶。
block 是每个有下界的块的下界点，bkcnt 是这个块的计数，S 是每个块的节点 vector。
vis 是临时的每个点是否属于簇路径，val 是每个点到它所属的簇的前缀和，tag 簇路径加的懒标记，sum 是簇路径的前缀和。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e4+5,mod=201314,B=400;
int n,m;
vector<int> e[maxn];
int dep[maxn],f[maxn],Fa[maxn],sz[maxn];
int up[maxn],down[maxn],uper[maxn],downer[maxn],stk[maxn],top=0,cnt=0;
int near[maxn],ind[maxn],st[maxn],Top=0,block[maxn],bkcnt=0;
vector<int> S[maxn];
bool vis[maxn];
int val[maxn],sum[maxn],tag[maxn];
inline void add(int x,int y){
if(y){
block[++bkcnt]=y,Fa[y]=x;//有下界点就记下下界点
//这个块的父亲是上界点，因为上界点是父亲簇的下界点
for(int now=y;now!=x;now=f[now])vis[now]=1;//给簇路径打上标记
}
for(int i=1;i<=top;i++){
int u=stk[i];
down[u]=y;
if(stk[i]!=y)up[u]=x;//下界点同时是下一个簇的上界点，上界点记为他自己
if(!y){near[u]=x;continue;}
int p=x;//求出near
for(int now=u;now!=x;now=f[now]){
if(vis[now]){p=now;break;}
if(near[now]){p=near[now];break;}
}
near[u]=p;
}
if(y)for(int now=y;now!=x;now=f[now])vis[now]=0;//恢复为0
}
void dfs(int u,int fa){
f[u]=fa;
for(auto it=e[u].begin();it!=e[u].end();it++)//删掉更方便
if((*it)==fa){e[u].erase(it);break;}
sz[u]=1;int Cnt=0;up[u]=0;
for(auto v:e[u]){
dep[v]=dep[u]+1,st[Top++]=v;
dfs(v,u);
if(up[v])++Cnt,up[u]=up[v];//计数儿子中的有界点的数量
//跟最后一个待在一个簇
sz[u]+=sz[v];
}
int y=0;//下界点
if(sz[u]>=B||u==1||Cnt>1){//分簇的三个条件
int Sz=0,ct=0;
for(int i=(int)e[u].size()-1;i>=0;i--){
int v=e[u][i];
Sz+=sz[v];
if(up[v])++ct;
if(Sz>B||ct>1){//避免有两个下界点接下去
Sz=sz[v],top=y=0,++cnt;
if(up[v])ct=1;
do{
stk[++top]=st[--Top];
y=max(y,up[st[Top]]);//不可言说
ind[st[Top]]=cnt;
S[cnt].push_back(st[Top]);// cnt 簇 中插入 st[Top]
}while(st[Top]!=e[u][i+1]);//不要插到别的子树去了
add(u,y);//u--y 为簇路径的簇
uper[cnt]=u,downer[cnt]=y;
}
}
top=y=0,++cnt;//还有一些点没进去
do{//和上面一样
stk[++top]=st[--Top];
y=max(y,up[st[Top]]);
ind[st[Top]]=cnt;
S[cnt].push_back(st[Top]);
}while(st[Top]!=e[u][0]);
add(u,y);
uper[cnt]=u,downer[cnt]=y;
up[u]=u,sz[u]=1;//现在只剩这个点自己了
}
}
inline void Addval(int u){//1--u ++
if(u==1)return ;//遇到根直接润
int tmp=(!Fa[u])?down[u]:0;//是否不是界点
for(int i=1;i<bkcnt;i++)sum[block[i]]-=sum[Fa[block[i]]];//最后一个是根
if(tmp)sum[tmp]+=dep[near[u]]-dep[up[u]];//簇路径的贡献
if(!Fa[u]){
int j=ind[u];
for(int i=(int)S[j].size()-1;i>=0;i--){//簇内部按深度排序
int x=S[j][i];
if(!Fa[f[x]])val[x]-=val[f[x]];//父亲不是界点：暂时把前缀和变成值
}
for(;!Fa[u]&&u>1;u=f[u])val[u]++;//路径暴力加
for(int i=0;i<S[j].size();i++){
int x=S[j][i];
if(!Fa[f[x]])val[x]+=val[f[x]];//再变回来
}
}
for(;u>=1;u=Fa[u])++tag[u],sum[u]+=dep[u]-dep[Fa[u]];//暴力加贡献
for(int i=bkcnt-1;i>=1;i--)sum[block[i]]+=sum[Fa[block[i]]];
}
inline int getans(int u){//1--u query
int bel=ind[u];
int res=val[u]*(downer[bel]!=u)+sum[up[u]];
//如果这是下界点，就无需统计块内前缀和；因为块间前缀和已经包含了它
if(!Fa[u]&&down[u])res+=(dep[near[u]]-dep[up[u]])*tag[down[u]];//不是界点就加上tag
return res;
}
struct query{
int id,u,z,w;
query(int a=0,int b=0,int c=0,int d=0){
id=a,u=b,z=c,w=d;
}
bool operator <(const query &b)const{return u<b.u;}
}q[maxn<<1];
bool cmp(int x,int y){
return dep[x]<dep[y];
}
int ans[maxn];
signed main(){
//这是离线做法的树分块代替树剖
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=2;i<=n;i++){
int x;cin>>x;x++;
e[x].push_back(i);e[i].push_back(x);
}
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;x++,y++,z++;
q[2*i-1]=query(i,y,z,1);q[2*i]=query(i,x-1,z,-1);
ans[i]=y-x+1;//根的处理比较特殊
//这里，我们把所有 dep 减一，贡献额外加上区间长
//好处就是不用管根的贡献。
}
sort(q+1,q+2*m+1);
dfs(1,0);
for(int i=1;i<=cnt;i++)sort(S[i].begin(),S[i].end(),cmp);
int now=0;
for(int i=1;i<=2*m;i++){
while(now<q[i].u)Addval(++now);
(ans[q[i].id]+=mod+q[i].w*getans(q[i].z)%mod)%=mod;
}
for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
return 0;
}
待补：FLOJ 4031
标签：cnt,int,Nityacke,++,st,Cluster,maxn,Top From： https://www.cnblogs.com/british-union/p/top-cluster.html