题解 P5903 【【模板】树上 k 级祖先】
skydogli
·
·
题解
这题，让我们深刻地体会到理论复杂度和实际复杂度的区别！
虽然没什么新东西，但是还是尝试了4种写法，就权当娱乐吧。
$\quad$时间复杂度$O(n+qlogn)
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int a=0,fh=1;char c=getchar();
while(c>57 or c<48){if(c=='-')fh=-1;c=getchar();}
while(47<c and c<58){
a=a*10+c-48;
c=getchar();
}
return a*fh;
}
#define MN 500005
int n,m,u,v,cnt,fa[MN],siz[MN],w[MN],top[MN],dep[MN],id[MN],ID[MN];
vector<int>edge[MN];
void dfs1(int x){
siz[x]=1;
for(int i=0;i<edge[x].size();++i){
fa[edge[x][i]]=x;
dep[edge[x][i]]=dep[x]+1;
dfs1(edge[x][i]);
siz[x]+=siz[edge[x][i]];
if(siz[w[x]]<siz[edge[x][i]])w[x]=edge[x][i];
}
}
void dfs2(int x){
id[x]=++cnt;
ID[cnt]=x;
if(w[x]){top[w[x]]=top[x];dfs2(w[x]);}
for(int i=0;i<edge[x].size();++i)
if(edge[x][i]!=w[x]){
top[edge[x][i]]=edge[x][i];
dfs2(edge[x][i]);
}
}
int rt;
int jump(int x,int k){
while(k>=id[x]-id[top[x]]+1&&x!=rt){
k-=(id[x]-id[top[x]]+1);
x=fa[top[x]];
}
return ID[id[x]-k];
}
#define ui unsigned int
ui S;
#define LL long long
inline ui get(ui x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return S = x;
}
int main(){
n=read();m=read();scanf("%u",&S);
rt=1;
for(int i=1;i<=n;++i){
fa[i]=read();
if(!fa[i])rt=i;
else edge[fa[i]].push_back(i);
}
dep[rt]=1;dfs1(rt);
top[rt]=rt;dfs2(rt);
LL ans=0;
int lstans=0;
for(int i=1;i<=m;++i){
int x=(get(S)^lstans)%n+1;
int k=(get(S)^lstans)%dep[x];
lstans=jump(x,k);
ans^=(LL)i*lstans;
}
printf("%lld\n",ans);
return 0;
}
```
- #### 基于树剖LCA的二分优化
$\quad$考虑如果我们定位到一个点的k级祖先在哪个重链上，我们就可以$O(1)$通过dfs序推出准确的位置，而一个点上面最多只有$logn$条重链，我们只要二分这个点在哪条重链即可（也可以倍增，而我实现时为了方便，直接在重链的顶端记上面所有重链的顶端）
$\quad$时间复杂度$O(nlogn+qloglogn)
code:
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int a=0,fh=1;char c=getchar();
while(c>57 or c<48){if(c=='-')fh=-1;c=getchar();}
while(47<c and c<58){
a=a*10+c-48;
c=getchar();
}
return a*fh;
}
#define MN 500005
int n,m,u,v,cnt,fa[MN],siz[MN],w[MN],top[MN],dep[MN],id[MN],ID[MN];
int FA[MN][19],CNT[MN];
vector<int>edge[MN];
void dfs1(int x){
siz[x]=1;
for(int i=0;i<edge[x].size();++i){
fa[edge[x][i]]=x;
dep[edge[x][i]]=dep[x]+1;
dfs1(edge[x][i]);
siz[x]+=siz[edge[x][i]];
if(siz[w[x]]<siz[edge[x][i]])w[x]=edge[x][i];
}
}
int rt;
void dfs2(int x){
id[x]=++cnt;
ID[cnt]=x;
if(top[x]==x){
int p=top[fa[top[x]]];
FA[x][0]=x;FA[x][1]=p;
for(int i=1;i<=CNT[p];++i)FA[x][i+1]=FA[p][i];
CNT[x]=CNT[p]+1;
}
if(w[x]){top[w[x]]=top[x];dfs2(w[x]);}
for(int i=0;i<edge[x].size();++i)
if(edge[x][i]!=w[x]){
top[edge[x][i]]=edge[x][i];
dfs2(edge[x][i]);
}
}
int jump(int x,int k){
if(k<id[x]-id[top[x]]+1) return ID[id[x]-k];
int y=top[x];
int l=0,r=CNT[y]+1;
while(l+1<r){
int mid=(l+r)>>1;
if(k<dep[x]-dep[FA[y][mid]]+1)r=mid;
else l=mid;
}
k-=dep[x]-dep[FA[y][l]]+1;
x=fa[FA[y][l]];
return ID[id[x]-k];
}
#define ui unsigned int
ui S;
#define LL long long
inline ui get(ui x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return S = x;
}
int main(){
n=read();m=read();scanf("%u",&S);
rt=1;
for(int i=1;i<=n;++i){
fa[i]=read();
if(!fa[i])rt=i;
else edge[fa[i]].push_back(i);
}
dep[rt]=1;dfs1(rt);
top[rt]=rt;dfs2(rt);
LL ans=0;
int lstans=0;
for(int i=1;i<=m;++i){
int x=(get(S)^lstans)%n+1;
int k=(get(S)^lstans)%dep[x];
lstans=jump(x,k);
ans^=(LL)i*lstans;
}
printf("%lld\n",ans);
return 0;
}
```
- #### 基于树剖LCA的分块
$\quad$考虑$\sqrt{logn}$和$loglogn$其实差不多，所以我们可以直接预处理出x的第$\sqrt{logn}$个祖先（3或4）,就可以一次跳多个祖先了。
$\quad$时间复杂度$O(n\sqrt{logn}+q\sqrt{logn})
code:
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int a=0;char c=getchar();
while(c>57 or c<48){c=getchar();}
while(47<c and c<58){
a=a*10+c-48;
c=getchar();
}
return a;
}
#define MN 500005
int n,m,u,v,cnt,fa[MN],siz[MN],w[MN],top[MN],dep[MN],id[MN],ID[MN],up[MN];
vector<int>edge[MN];
const int len=3;
void dfs1(int x){
siz[x]=1;
for(int i=0;i<edge[x].size();++i){
fa[edge[x][i]]=x;
dep[edge[x][i]]=dep[x]+1;
dfs1(edge[x][i]);
siz[x]+=siz[edge[x][i]];
if(siz[w[x]]<siz[edge[x][i]])w[x]=edge[x][i];
}
}
void dfs2(int x){
id[x]=++cnt;
ID[cnt]=x;
if(w[x]){top[w[x]]=top[x];dfs2(w[x]);}
if(x==top[x]){
int p=x;
for(int i=1;i<=len;++i){if(top[fa[p]]==1)break;p=top[fa[p]];}
up[x]=p;
}
else up[x]=up[top[x]];
for(int i=0;i<edge[x].size();++i)
if(edge[x][i]!=w[x]){
top[edge[x][i]]=edge[x][i];
dfs2(edge[x][i]);
}
}
int rt;
int jump(int x,int k){
while(k>=dep[x]-dep[up[x]]+1){
k-=(dep[x]-dep[up[x]]+1);
x=fa[up[x]];
}
while(k>=id[x]-id[top[x]]+1){
k-=(id[x]-id[top[x]]+1);
x=fa[top[x]];
}
return ID[id[x]-k];
}
#define ui unsigned int
ui S;
#define LL long long
inline ui get(ui x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return S = x;
}
int main(){
n=read();m=read();scanf("%u",&S);
rt=1;
for(int i=1;i<=n;++i){
fa[i]=read();
if(!fa[i])rt=i;
else edge[fa[i]].push_back(i);
}
dep[rt]=1;dfs1(rt);
top[rt]=rt;dfs2(rt);
LL ans=0;
int lstans=0;
for(int i=1;i<=m;++i){
int x=(get(S)^lstans)%n+1;
int k=(get(S)^lstans)%dep[x];
lstans=jump(x,k);
ans^=(LL)i*lstans;
}
printf("%lld\n",ans);
return 0;
}
```
- #### 长链剖分
$\quad$ 终于到了正解~~但它随机数据是真的没优势~~
$\quad$ 我们考虑以最深深度的儿子为重儿子，然后记录这条链的所有节点（记录自顶向下第i个点是什么）和这条链顶上的相当于链长的信息。另外还要倍增出每个节点向上$2^p$个节点的父亲，对于每次查询的k，我们先把x跳到k第一个二进制位代表的数的位置，这样就可以把剩下的距离缩减到$\lfloor\frac{k}{2}\rfloor$以下，这样，当前这个节点的链长肯定比剩下要跳的长度更大了，所以直接向上跳即可。
另外，因为维护的信息等于链长，所以我们可以用每个点记录这个信息，就不用开```vector```了
$\quad$时间复杂度$O(nlogn+q)
code:
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int a=0;char c=getchar();
while(c>57 or c<48){c=getchar();}
while(47<c and c<58){
a=a*10+c-48;
c=getchar();
}
return a;
}
#define MN 500005
int n,m,u,v,cnt,fa[MN][21],w[MN],h[MN];
int Log[MN],top[MN],dep[MN],id[MN],U[MN],D[MN];
vector<int>edge[MN];
void dfs1(int x){
for(int i=1;i<=19;++i)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=0;i<edge[x].size();++i){
dep[edge[x][i]]=h[edge[x][i]]=dep[x]+1;
dfs1(edge[x][i]);
h[x]=max(h[x],h[edge[x][i]]);
if(h[edge[x][i]]>h[w[x]])w[x]=edge[x][i];
}
}
void dfs2(int x,int p){
id[x]=++cnt;
D[cnt]=x;
U[cnt]=p;
if(w[x]){top[w[x]]=top[x];dfs2(w[x],fa[p][0]);}
for(int i=0;i<edge[x].size();++i)
if(edge[x][i]!=w[x]){
top[edge[x][i]]=edge[x][i];
dfs2(edge[x][i],edge[x][i]);
}
}
int rt;
#define ui unsigned int
ui S;
#define LL long long
inline ui get() {
S ^= S << 13;
S ^= S >> 17;
S ^= S << 5;
return S;
}
inline int ask(register int x,register int k){
if(!k)return x;
x=fa[x][Log[k]];k-=(1<<Log[k]);
k-=dep[x]-dep[top[x]];x=top[x];
if(k>=0) return U[id[x]+k];
return D[id[x]-k];
}
int main(){
n=read();m=read();scanf("%u",&S);
Log[0]=-1;
for(int i=1;i<=n;++i)Log[i]=Log[i>>1]+1;
rt=1;
for(int i=1;i<=n;++i){
fa[i][0]=read();
if(!fa[i][0])rt=i;
else edge[fa[i][0]].push_back(i);
}
dep[rt]=1;dfs1(rt);
top[rt]=rt;dfs2(rt,rt);
LL ans=0;
int lstans=0;
for(int i=1;i<=m;++i){
register int x=(get()^lstans)%n+1,k=(get()^lstans)%dep[x];
lstans=ask(x,k);
ans^=(LL)i*lstans;
}
printf("%lld\n",ans);
return 0;
}
```
当然，这个表现和询问随机有很大的关系，况且多学一个做法也不是坏事。