上一篇：树链剖分学习笔记（一）
这篇是长链剖分
并没有仔细研究过这方面的内容，所以就随便写点简单的东西了
1. 概念
长链剖分也是一种树链剖分，所以和轻重链剖分很相似
区别是长链剖分选择子树深度最大的儿子作为重儿子，而不是子树大小最大的
它也具有一些性质：
-
链长总和是 \(O(n)\) 级别的
好像是句废话 -
任意节点 \(x\) 的 \(k\) 级祖先 \(y\) 所在的长链的长度大于等于 \(k\)
\(y\) 到 \(x\) 这条链的长度为 \(k\) ，而显然 \(y\) 所在的长链不可能比它短 -
任意节点 \(x\) 到根节点的路径最多包含 \(O(\sqrt n)\) 条长链
从 \(x\) 向上跳，若到达新的长链上，则该链的长度必然大于之前那条链的长度
所以最坏情况下经过的长链的长度依次为 \(1,2,3,\cdots\)
链长总和为 \(O(n)\) 级别，故链的条数为 \(O(\sqrt n)\) 级别
2. 应用
这里只讲一道例题 因为只做了一道
题意：求节点 \(x\) 的 \(k\) 级祖先 \(y\)，多组询问，强制在线
算个模板题吧
令 \(h={\rm highbit}(k)\) 表示 \(k\) 的最高二进制位，则 \(h>k/2\)
倍增预处理所有 \(2^a\) 级祖先，则回答询问时我们可以先直接跳到 \(x\) 的 \(h\) 级祖先 \(z\)
然后 \(z\) 所在的长链长度大于等于 \(h\)
那么 \(k\) 级祖先应该就在这条链或者其上端的那条长链上
凭直觉感受的话这东西应该能 \(O(1)\) 求了
设 \(z\) 所在长链长度为 \(len\) ，顶端节点为 \(top\)
从 \(z\) 开始还需向上跳 \(k-h\) 次
故 \(y\) 与 \(top\) 的距离为 \((dep_z-dep_{top})-(k-h)\)
距离为正则 \(y\) 是 \(top\) 的儿子，为负则 \(y\) 是 \(top\) 的祖先
对于每个 \(top\) ，向上预处理前 \(len\) 级祖先，向下处理前 \(len\) 级儿子
于是就实现了 \(O(1)\) 查询
而这一步预处理的时间复杂度为 \(O(\sum len)\) ，也就是 \(O(n)\)
总时间复杂度为 \(O(n\log n+m)\)
可以发现倍增预处理是复杂度瓶颈，故只有像本题这样询问量很大时长链剖分才具有优势
#include<stdio.h>
#include<ctype.h>
#include<vector>
#define gc (l==r&&(r=(l=c)+fread(c,1,1<<21,stdin),l==r)?EOF:*l++)
const int N=300010; int n,m,lgn,cnt,x,y,k,len,t,ans;
int last[N],dep[N],depm[N],top[N],son[N],hb[N];
struct node { int y,pre; }E[N<<1];
std::vector<int>a[N],b[N]; int sa[N],sb[N],f[N][20];
void dfs(int x,int fa) {
depm[x]=dep[x]=dep[fa]+1,f[x][0]=fa; // depm: x 的子树中节点的最大深度
for (int i=0; i<lgn; ++i)
f[x][i+1]=f[f[x][i]][i]; // 倍增预处理
for (int i=last[x],y; i; i=E[i].pre)
if ((y=E[i].y)!=fa) {
dfs(y,x);
if (depm[y]>depm[x])
son[x]=y,depm[x]=depm[y];
}
}
void dfs2(int x,int tx) {
top[x]=tx;
if (!son[x]) return ;
dfs2(son[x],tx);
for (int i=last[x],y; i; i=E[i].pre)
if (!top[y=E[i].y]) dfs2(y,y);
}
int p=-1,p2,num[9];
char c[1<<21],*l=c,*r=c,cw[1<<21];
int read() { // fread 读入优化
int x=0; char ch=gc;
while (!isdigit(ch)) ch=gc;
while (isdigit(ch)) x=x*10+(ch^48),ch=gc;
return x;
}
inline void flush() { fwrite(cw,1,p+1,stdout),p=-1; }
void write(int x) { // fwrite 输出优化
p>>20&&(flush(),0);
do num[++p2]=x%10; while (x/=10);
do cw[++p]=(num[p2]^48); while (--p2);
cw[++p]='\n';
}
int main() {
n=read(),lgn=-1;
for (int i=1; i<=n; i<<=1) ++lgn;
for (int i=1; i<n; ++i)
x=read(),y=read(),
E[++cnt]={y,last[x]},last[x]=cnt,
E[++cnt]={x,last[y]},last[y]=cnt;
dfs(1,0),dfs2(1,1);
for (int i=1,j=0; i<=n; ++i) // 预处理 highbit
i==(1<<j+1)&&(++j),hb[i]=j;
for (int i=1; i<=n; ++i) if (top[i]==i) {
len=depm[i]-dep[i];
for (int j=0,t=i; j<=len; ++j,t=f[t][0])
a[i].push_back(t); // 祖先
for (int j=0,t=i; j<=len; ++j,t=son[t])
b[i].push_back(t); // 儿子
sa[i]=a[i].size(),sb[i]=b[i].size();
}
m=read();
while (m--) {
x=read()^ans,k=read()^ans;
if (k) {
x=f[x][hb[k]],y=top[x];
t=dep[x]-dep[y]-k+(1<<hb[k]);
if (t<0) ans=(-t>=sa[y]?0:a[y][-t]);
else ans=(t>=sb[y]?0:b[y][t]);
}
else ans=x;
write(ans);
}
return flush(),0;
}