长链剖分也是一种树上的链剖分的方法。与重链剖分不同,长链剖分对于树上的每个点,取子树深度最大的儿子,向它连重边,其他的儿子向它连轻边。容易发现一个点所在的重链的长度至少为它子树的深度。
利用这个性质可以\(O(nlogn)\)预处理,\(O(1)\)求树上任意节点的k级祖先。比如当前要询问点x的k级祖先(k>0),我们取k的二进制表示中最高的1,令这个1表示的是\(2^a\)。我们先用倍增(\(O(nlogn)\)预处理)求出x的\(2^a\)级祖先y。接下来需要求y的\(k-2^a\)级祖先。根据上面说的性质,y所在的重链一定至少有\(2^a\)个点,令这条链的长度为len,链中深度最浅的点为z。由于\(2^a>k-2^a\),所以y的\(k-2^a\)级祖先要么在这条链中,要么从z往父亲方向走最多\(2^a\)步一定能走到。为了\(O(1)\)询问,只要对每一条重链,对它最浅的点预处理出从它向上走len步形成的链,以及这条链本身的所有点就可以了。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
#define ui unsigned int
ui s;
inline ui get(ui x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return s = x;
}
int n,q,root,dep[500010],mxd[500010],fa[500010][22],top[500010];
vector <int> g[500010],v[500010],vv[500010];
void dfs(int pos,int d)
{
dep[pos]=mxd[pos]=d;
pii lk=mpr(-1,-1);
rep(i,g[pos].size())
{
fa[g[pos][i]][0]=pos;
dfs(g[pos][i],d+1);
mxd[pos]=max(mxd[pos],mxd[g[pos][i]]);
lk=max(lk,mpr(mxd[g[pos][i]],g[pos][i]));
}
if(lk.fi>-1)
{
rep(i,g[pos].size()) if(g[pos][i]!=lk.se)
{
int len=mxd[g[pos][i]]-dep[g[pos][i]]+1,u=g[pos][i];
rep(j,len)
{
v[g[pos][i]].pb(u);
u=fa[u][0];if(u==0) break;
}
}
}
}
void dfs2(int pos,int tp)
{
if(v[pos].size()>0) tp=pos;
top[pos]=tp;
vv[tp].pb(pos);
rep(i,g[pos].size()) dfs2(g[pos][i],tp);
}
int getAnces(int x,int k)
{
int tp=top[x];
if(k<=dep[x]-dep[tp])
{
int need=dep[x]-dep[tp]-k;
return vv[tp][need];
}
else
{
int need=k-(dep[x]-dep[tp]);
return v[tp][need];
}
}
int main()
{
fileio();
cin>>n>>q>>s;
int x;
repn(i,n)
{
scanf("%d",&x);
if(x==0) root=i;
else g[x].pb(i);
}
dfs(root,1);
v[root]={root};
rep(i,20) repn(j,n) fa[j][i+1]=fa[fa[j][i]][i];
dfs2(root,root);
int lstans;
LL ans=0;
rep(qn,q)
{
int x=(get(s)^(ui)lstans)%n+1,k=(get(s)^(ui)lstans)%dep[x];
if(k>0)
{
int lev=31-__builtin_clz(k);
x=fa[x][lev];k^=(1<<lev);
}
lstans=getAnces(x,k);
ans^=(LL)(qn+1)*lstans;
}
cout<<ans<<endl;
termin();
}
原文地址:http://www.cnblogs.com/legendstane/p/long-chain-split-kth-ancestor.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性