top cluster

一个树簇（$\text{cluster}$）是一个联通子图，至多有两个点和全树的其他位置连接。

这两个点称为界点（$\text{boundary node}$），不是界点的点称为内点（$\text{internal node}$），这两个界点间的路径称为簇路径（$\text{cluster path}$）。

簇可以通过 $\text{compress}$ 和 $\text{rake}$ 合并，但这里不是重点，就不展开了。

树分块

要求将原树划分为 $O(\frac{n}{B})$ 个不交簇的并，每个簇大小均为 $O(B)$。

将界点看做点，簇看做边，形成的树被称作收缩树。

构造方法

$\text{dfs}$ 的时候维护一个栈存放未归类的边。

我们只在三种情况下把当前点作为界点，并将边弹出。

• 当前点为根节点；
• 当前点的儿子中存在两个及以上含有界点的子树；
• 栈中边数量大于 $B$。

问题抽象为给定两个序列 $a$，$b$。将序列划分为若干段使得每个子段 $\sum b$ 不超过 $1$，$\sum a$ 不超过 $B$。

直接贪心地取最长的合法前缀就可以了。

这样实现的块的数量最多为 $6\frac {n}{B}$。

实现

UPD：这个实现太烂了，我回头重写一下。

随便找了道链加链求和的题。

P4211 [LNOI2014]LCA

#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
struct que{
	int id,kt,t;
	que(int const &i=0,int const &k=0,int const &p=0):
		id(i),kt(k),t(p){}
}t[100010];
int hd[50010],nt[100010];
void add(int const &x,que const &y){
	static int cnt=0;
	t[++cnt]=y,nt[cnt]=hd[x],hd[x]=cnt;
}
int const B=200;
std::vector<int> v[50010],s[50010];
int st[50010],tp,book[50010],bk[50010],bel[50010],a[50010],b[50010],cnt,f[50010],bf[50010],L[50010],R[50010];
void link(int x,int y){
	bf[y]=x,v[x].push_back(y);
	while(y!=x)bk[y]=1,y=f[y];
}
void dfs(int const &x){
	int k=tp,ct=0;
	std::vector<int> &son=s[x]; 
	for(auto const &to:son){
		st[tp++]=to,f[to]=x;
		dfs(to);
		if(b[to])++ct,b[x]=b[to];
	}
	if(x==1||ct>1||tp-k>=B){
		book[x]=1;
		b[x]=x;
		int sz=0,lst=son.size()-1;ct=0;
		for(unsigned i=son.size()-1;~i;i--){
			sz+=a[son[i]];
			if(b[son[i]])++ct,link(x,b[son[i]]);
			if(sz>B||ct>1){
				sz=a[son[i]];
				if(b[son[i]])ct=1;
				++cnt;do bel[st[--tp]]=cnt; while(st[tp]!=son[i+1]);
				L[cnt]=i+1,R[cnt]=lst,lst=i; 
			}
		}
		++cnt;do bel[st[--tp]]=cnt; while(st[tp]!=son[0]);
		L[cnt]=0,R[cnt]=lst; 
	}
	a[x]=tp-k+1;
}
int dis[50010],top[50010];
void dfs2(int const &x,int const &tp=0){
	int d=dis[x];
	if(book[x])d=0;
	top[x]=tp;
	for(auto const &to:s[x]){
		top[to]=top[x];
		if(bk[to])dis[to]=d+1;
		else dis[to]=d;
		dfs2(to,book[x]?x:top[x]);
	}
}
int vv[50010],w[50010],d[50010],tag[50010],p[50010];
void dfs3(int const &x,int const &k){
	for(auto const &to:s[x]){
		d[to]=d[x]+vv[to];
		if(!book[to])dfs3(to,k);
		else w[to]=tag[k]*dis[to]+d[to];
	}
}
void dfs4(int const &x){for(auto const &to:v[x])p[to]=p[x]+w[to],dfs4(to);}
void update(int x){
	if(x==1) return;
	int k=bel[x];
	do ++vv[x],x=f[x]; while(!book[x]);
	for(int i=L[k];i<=R[k];i++){
		int to=s[x][i];
		d[to]=vv[to];
		if(!book[to]) dfs3(to,k);
		else w[to]=tag[k]*dis[to]+d[to];
	}
	while(x!=1) ++tag[bel[x]],w[x]+=dis[x],x=bf[x];
	dfs4(1);
}
int query(int x){return tag[bel[x]]*dis[x]+d[x]+p[top[x]];}
long long ans[50010];
int n,q;
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=2,x;i<=n;i++)scanf("%lld",&x),s[x+1].push_back(i);
	dfs(1),dfs2(1);
	for(int i=1,l,r,z;i<=q;i++)scanf("%lld%lld%lld",&l,&r,&z),add(l,que(i,-1,z+1)),add(r+1,que(i,1,z+1));
	for(int i=1,j;i<=n;i++)
		for(update(i),j=hd[i];j;j=nt[j])
			ans[t[j].id]+=t[j].kt*(query(t[j].t)+i);
	for(int i=1;i<=q;i++)printf("%lld\n",(ans[i]%201314+201314)%201314);
	return 0;
}