算法简介
\(\quad\)这个数据结构的重儿子是深度最深的节点，这是它和树链剖分唯一的区别。
\(\quad\)它最经典的应用就是求 k 级祖先，预处理的期望复杂度为 O(nlogn)，查询 O(1)
\(\quad\)设每个节点的重儿子深度为 hson ， 每个轻儿子记录往上 hson 长度路径的信息，每一条链头记录自己这条链的信息，都用 vector 存下来。
\(\quad\)查询就是先倍增跳，然后再利用 vector 的信息直接输出。
例题
#include<bits/stdc++.h>
using namespace std;
const int maxn=500010;
vector<int> g[maxn],up[maxn],down[maxn];
int binh[500010],dep[500010],h[500010],hson[500010],tp[500010],fa[500010][20];
struct
{
int nxt,v;
}e[maxn];
int head[maxn],cnt;
unsigned int s;//题目中给的种子
inline unsigned int get(unsigned int x)//题目中给的随机函数
{
x^=x<<13;
x^=x>>17;
x^=x<<5;
return s=x;
}
void add(int u,int v)
{
cnt++;
e[cnt].nxt=head[u];
e[cnt].v=v;
head[u]=cnt;
}
void dfs(int x,int f)
{
dep[x]=dep[f]+1;
fa[x][0]=f;
for(int i=1;i<20;i++)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
}
h[x]=-1;
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==f) continue ;
dfs(v,x);
if(h[v]>h[x])
{
hson[x]=v;
h[x]=h[v];
}
}
h[x]++;
if(!h[x]) h[x]=1;
}
void dfs2(int x,int ttp)
{
down[ttp].push_back(x);
tp[x]=ttp;
if(!hson[x]) return ;
dfs2(hson[x],ttp);
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;
if(v!=hson[x] && v!=fa[x][0])
{
up[v].push_back(v);
for(int j=1;j<=h[v];j++)
{
up[v].push_back(fa[up[v].back()][0]);
}
dfs2(v,v);
}
}
}
int main()
{
int n,q;
cin>>n>>q;
int root,x,k,lastans=0;
long long out=0;
cin>>s;
for(int i=1;i<=n;i++)
{
cin>>x;
if(!x) root=i;
else
{
add(x,i);
}
binh[i]=log2(i);
}
dfs(root,root);
dfs2(root,root);
for(int i=1;i<=q;i++)
{
x=(get(s)^lastans)%n+1;
k=(get(s)^lastans)%dep[x];
if(!k)
{
lastans=x;
out^=1ll*i*x;
continue ;
}
int tod=dep[x]-k;
x=tp[fa[x][binh[k]]];
int tpd=dep[x];
if(tpd<tod) x=down[x][tod-tpd];
else x=up[x][tpd-tod];
lastans=x;
out^=1ll*i*x;
}
cout<<out;
return 0;
}
注意
\(\quad\)尽管长链剖分的理论复杂度很优秀，但是在随机数据下有时还不如树剖LCA优秀，而且打起来也有点麻烦，所以一般情况不建议使用。但是如果询问很多的话，那长链剖分的优势就会体现出来。