P5903 【模板】树上 K 级祖先

非长链剖分解法！！！

k级祖先问题，依然考虑树链剖分。

我们首先进行重链剖分，求x的k级祖先，就从x开始往上跳，然后就解决了。最后跑的比绝大多长链剖分做法都快。(洛谷最优解第二页)...

#include<bits/stdc++.h>
using namespace std;
#define ui unsigned int
#define ll long long
const int N=5e5+10;

int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}

ui s;
int n,q,rt,head[N],tot;
int fa[N],dep[N],sz[N],son[N],top[N],dfn[N],idx,DFN[N];
struct node{
int to,nxt;
}edge[N*2];
void add(int x,int y){
edge[++tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}

void dfs1(int x,int father){
sz[x]=1,dep[x]=dep[father]+1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y==father) continue;
dfs1(y,x);
sz[x]+=sz[y];
if(sz[son[x]]<sz[y]) son[x]=y;
}
}

void dfs2(int x,int t){
top[x]=t,dfn[x]=++idx,DFN[idx]=x;
if(!son[x]) return;
dfs2(son[x],t);
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}

int k_ancestor(int x,int k){
while(k>=dfn[x]-dfn[top[x]]+1&&x!=rt){
k-=dfn[x]-dfn[top[x]]+1;
x=fa[top[x]];
}
return DFN[dfn[x]-k];
}

ui get(ui x){
x^=x<<13,x^=x>>17,x^=x<<5;
return s=x;
}

int main(){

n=read(),q=read(),cin>>s;int T=0;
for(int i=1;i<=n;i++){
fa[i]=read();
if(!fa[i]) rt=i;
else add(fa[i],i),add(i,fa[i]);
}
dfs1(rt,0),dfs2(rt,rt);
int la=0;ll ans=0;
while(q--){
T++;
int x=((get(s)^la)%n)+1,k=(get(s)^la)%dep[x];
la=k_ancestor(x,k),ans^=(ll)T*la;
}
cout<<ans<<endl;

return 0;
}

原文地址：https://blog.csdn.net/summ1ts/article/details/142389190

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！