性质
性质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 | } |
因为$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$
我们先表示出要求的东西，我们想办法把到$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 | } |