起因是有人在la群问
已知u是v的祖先,求u到v路径上第一个点.
怎么写比较简单.
突然想起很久之前我在la板子上写过一个题解区里没有看到的简洁做法.
有一个不难证明的结论,一个节点u的k级祖先v对应深度的所有节点中dfn序中小于等于u的最后一个点.
考虑dfn序的性质,u一定在v所在的子树的这段区间中,因此得证.
开vector然后二分即可.
复杂度 O(n+qlogn) 常数较小(一次跑不满的二分).
code
#include<bits/stdc++.h>
using i64=long long;
using u32=unsigned;
using std::cin;
using std::cout;
u32 s;
u32 get(u32 x){
x^=x<<13;
x^=x>>17;
x^=x<<5;
return s=x;
}
void solve(){
int n,q;
cin>>n>>q>>s;
std::vector<int> fa(n+1),dfn(n+1),rnk(n+1),dep(n+1);
std::vector<std::vector<int> > G(n+1),Z(n+1);
for(int i=1;i<=n;++i){
cin>>fa[i];
G[fa[i]].emplace_back(i);
}
int ti=0;
auto dfs=[&](auto&&self,int u,int d)->void{
rnk[ti]=u,dfn[u]=ti,dep[u]=d;
Z[d].emplace_back(ti),++ti;
for(auto to:G[u]){
self(self,to,d+1);
}
};
dfs(dfs,0,0);
i64 ans=0,las=0;
for(int i=1;i<=q;++i){
int x=(get(s)^las)%n+1,k=(get(s)^las)%dep[x];
las=rnk[*prev(upper_bound(Z[dep[x]-k].begin(),Z[dep[x]-k].end(),dfn[x]))];
ans^=i*las;
}
cout<<ans;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
return 0;
}
// https://www.luogu.com.cn/problem/P5903