性质

性质1：对树长链剖分后，树上所有长链的长度和为$n$

性质2：对于树上任意一点$x$，它的$K$级祖先$y$所在长链的长度一定$\ge K$。

性质3：从任何一个点向上跳到根所经过的轻边不会超过$\sqrt n$条

适用范围

1.维护子树中只与深度有关的信息，$O(n)$统计每个点子树中可合并的以深度为下标的信息。

2.单次$O(1)$在线查询一个点的$k$级祖先。

实现

按照子树深度剖分，与深度最深的儿子连成链

对于重儿子用$O(1)$时间继承信息，轻儿子直接改

1

inline void dfs1(re int x,re int prt,re int depth){

2

	re int i,y;maxd[x]=dep[x]=depth;fa[x]=prt;size[x]=1;

3

	for(i=h[x];i;i=e[i].next){

4

		y=e[i].to;if(y==prt)continue;

5

		dfs1(y,x,depth+1);size[x]+=size[y];

6

		if(maxd[y]>maxd[x]){maxd[x]=maxd[y];son[x]=y;}

7

	}

8

}

9

inline void dfs2(re int x,re int Top){

10

	re int i,y;top[x]=Top;st[x]=++tot;

11

	if(!son[x])return;

12

	dfs2(son[x],Top);

13

	for(i=h[x];i;i=e[i].next){

14

		y=e[i].to;if(y==prt||y==son[x])continue;

15

		dfs(y,y);

16

	}

17

}

运用

1.$O(1)$求$K$级祖先

第一步预处理

• $ST$预处理出每个点的$2^K$级祖先
• 对于所有$K(1-n)$ ，我们把这个$K$转换成二进制表示，记录它的位数$log_K$
  显然有$2log_K\geq \frac{K}{2}$
• 设$len_x$为节点$x$所属长链的长度，对于所有长链的顶端节点$tp$，我们记录$tp$上方和下方的$len_{tp}−1$个节点。

1

void dfs1(re int x,re int prt,re int depth){

2

	re int i,y;

3

	*dp[x]=prt;maxd[x]=dep[x]=depth;

4

	for(i=h[x];i;i=e[i].next){

5

		y=e[i].to;if(y==prt)continue;

6

		dfs1(y,x,depth+1);

7

		if(maxd[x]<maxd[y]){maxd[x]=maxd[y];son[x]=y;}

8

	}

9

}

10

void dfs2(re int x,re int Top){

11

	re int i,y;top[x]=Top;

12

	len[x]=maxd[x]-dep[Top]+1;

13

	if(!son[x])return;

14

	dfs2(son[x],Top);

15

	for(i=h[x];i;i=e[i].next){y=e[i].to;if(y==*dp[x]||y==son[x])continue;dfs2(y,y);}

16

}

17

inline void ST(void){

18

	re int i,j;

19

	for(j=1;j<=18;++j)

20

		for(i=1;i<=n;++i)dp[i][j]=dp[dp[i][j-1]][j-1];

21

	*tot=-1;for(i=1;i<=n;++i)tot[i]=tot[i>>1]+1;

22

}

23

inline int LCA(re int x,re int y){

24

	re int i;

25

	if(dep[x]<dep[y])swap(x,y);

26

	for(i=18;~i;--i)if(dep[dp[x][i]]>=dep[y])x=dp[x][i];

27

	if(x==y)return x;

28

	for(i=18;~i;--i)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}

29

	return *dp[x];

30

}

31

inline void Inc(void){

32

	re int i,j,tp,sum,tmp;sum=0;

33

	for(i=1;i<=n;++i){

34

		tp=top[i];if(vis[tp])continue;vis[tp]=1;

35

		idx[tp]=sum+len[tp];save[idx[tp]]=tp;

36

		tmp=tp;for(j=idx[tp]-1;j>idx[tp]-len[tp];--j){tmp=son[tmp];save[j]=tmp;}

37

		tmp=tp;for(j=idx[tp]+1;j<idx[tp]+len[tp];++j){tmp=*dp[tmp];save[j]=tmp;}

38

		sum+=2*len[tp]-1;

39

	}

40

}

然后处理询问:

设询问的点是$x$，要找它的$K$级祖先$fa$

首先利用$ST$从询问点$x$上跳 $2^{log_K}$步，把上跳后这个点叫$y$。

那么因为$2^{log_K}\geq \frac{K}{2}$，我们至少跳了$K \over 2$步。

此时根据性质$2$，$y$所在长链的长度$len_y\geq \frac{K}{2}$。

设$tp$为$y$所在长链的顶端节点。

则在$tp$上方的第$(K−2^{log_K})−Dis(y,tp)$个点。（负数为下方，$0$就是$tp$本身）

1

inline int Query(re int x,re int k){

2

	re int tp;if(k>dep[x])return 0;if(!k)return x;

3

	x=dp[x][tot[k]];k-=1<<tot[k];

4

	tp=top[x];return save[idx[tp]+k-(dep[x]-dep[tp])];	

5

}

模板题

$BSOJ5187$or$BSOJ5385$

因为$k$的大小不确定，所以分情况来做。设$Lim=\sqrt{n}$，当$k\le Lim$时，可以预处理出$sum[i][j]$表示$i$节点以$j$步伐一直往上走，直到走到根节点($i$节点的深度如果不是$k$的倍数，根节点不计入)为止能得到的点权和，查询时直接求就好了.当$k>Lim$时,就要暴力往上走了用长链剖分$O(1)$查询一个点的k级祖先，因此最多爬$\sqrt{n}$次;

单次查询时间复杂度$O(\sqrt{n})$。

2.$O(n)$继承信息优化$dp$

$BSOJ6308$

我们先表示出要求的东西，我们想办法把到$x$的距离$\leq k$的点权和转化为与在$x$的子树中到$x$的距离$\leq k$的点权和

设$\displaystyle{f_{x,k}}$表示在$x$的子树中到$x$的距离$\leq k$的点权和

$fa^x_k表示$x$的$k$级父亲

则$\displaystyle{Ans_{x,K}=f_{x,K}+\sum_{k=1}^{\min{\{dep_x,K\}}}f_{fa^x_k,K-k}-f_{x,K-2k}}$

后面的是对于每一个$x$的$k$级父亲，我们求出在它的子树中但又不在$x$的子树中的，距离它$K-k$距离的点权和

因此也就等价于，在$x$上面距离$x$不超过$K$的距离和

用这道题来讲一下如何使用长链剖分

为了能$O(n)$完成重儿子继承，我们换一种设法

新设$f_{id_x+k}$表示$x$子树内距离不超过$k$的点权和

这样设有什么好处呢，对于$x$的重儿子$y$,$f_{id_x+k}=f_{(id_y+1)+k}=f_{id_y+(k+1)}$,不用赋值就继承了来自下方的信息

然后就可以转移了,贴一下老师的分析

重儿子直接继承完毕后:

$j=0,f_{id_x}=a_x$

$1\leq j\leq len_x，f_{id_x+j}+=a_x$

设轻儿子为$y$，$x$点权值为$a_x$，暴力维护时注意判断一下$j$和$len_y$的大小

$1\leq j\leq len_{y}+1，则f_{id_x+j}+=f_{id_y+j-1}$

$len_{y}+2\leq j\leq len_{x}，则f_{id_x+j}+=f_{id_y+len_{y}}$

$修改一下形式：$

$1\leq j\leq len_{y}+1，则f_{id_x+j}+=f_{id_y+j-1}-f_{id_y+len_{y}}；$

$1\leq j\leq len_{x}，则f_{id_x+j}+=f_{id_y+len_{y}}$

重链的循环需要优化掉：

$将f_{id_y+leny}累积到sum_{id_x}中$

$1\leq j\leq len_{y}+1，则f_{id_x+j}+=f_{id_y+j-1}-f_{id_y+len_{y}}；$

$sum_{id_x}+=f_{id_y+len_{y}}$

$由于f_{id_x+0}不需要累加sum_{id_x}，所以需要先提前减去，于是$

$f_{id_x}-=-sum_{id_x}$

$sum_{id_x}+=w_{x}$

$0\leq j\leq len_{x}，f_{id_x+j}+=sum_{id_x}$

$现在尝试优化掉最后一个重链循环（因为只有轻链可以暴力维护，重链暴力维护时间复杂度会变化）：$

$实际上只需要在使用f数组的时候和sum数组打包即可，不需要每次把sum数组加入到f数组的结果中，此时相当于把原本的f拆成了f和sum两部分。注意，此时重儿子直接继承过来f时，sum没有直接继承过来，所以现在要另外对sum进行继承了$

$重儿子f数组直接继承，sum数组现在需要单独继承$

$sum_{id_x}=sum_{id_{son_{x}}}$

$1\leq j\leq len_{y}+1，则f_{id_x+j}+=f_{id_y+j-1}+sum_{id_y}-f_{id_y+leny}-sum_{id_y}；$

$原本所有使用f的地方都变成f+sum$

$sum_{id_x}+=f_{id_y+leny}+sum_{id_y}$

$f_{id_x}-=sum_{id_x}$

$sum_{id_x}+=w_{x}$

$同时更新答案时使用f_{id_x+k}+sum_{id_x}即可$

1

inline void Solve(re int x){

2

	re int i,j,y,leny;if(son[x]){Solve(son[x]);sum[idx[x]]=sum[idx[son[x]]];}

3

	for(i=h[x];i;i=e[i].next){

4

		y=e[i].to;

5

		if(y==fa[x]||y==son[x])continue;

6

		Solve(y);leny=maxd[y]-dep[y];

7

		for(j=1;j<=leny+1;++j)dp[idx[x]+j]+=dp[idx[y]+j-1]+sum[idx[y]]-(dp[idx[y]+leny]+sum[idx[y]]);

8

		sum[idx[x]]+=dp[idx[y]+leny]+sum[idx[y]];

9

	}

10

	dp[idx[x]]-=sum[idx[x]];sum[idx[x]]+=a[x];

11

	for(i=hq[x];i;i=eq[i].next){

12

		y=eq[i].to;

13

		ans[y]+=eq[i].opt*(sum[idx[x]]+dp[min(1ll*idx[x]+eq[i].k,1ll*idx[x]+maxd[x]-dep[x])]);

14

	}

15

}