Vijos lxhgww的奇思妙想–求K级祖先

给出一棵树求K级祖先。O(N*logN+Q)

更详细的讲解见:https://www.cnblogs.com/cjyyb/p/9479258.html

/*
要求k级祖先，我们可以把k拆成"2^highbit(x)+tmp 形式
(highbit(x)为x在二进制位下的最高位)，然后用倍增的方法把highbit(x)的部分跳了
剩下tmp的同样可以预处理掉，这样预处理就是O(n*logn)的效率,
所以对于每个询问就是O(1)回答，这样的效率就是O(n*logn+q)。
于是就考虑用长链剖分。
讲讲具体的细节操作。
数组：
f[i][j]:i的倍增得到的祖先
d[i]:i i的最深的儿子的深度（用于处理len lenlen）
dep[i]:i的节点深度
son[i]:i的长儿子
len[i]:i为长链顶点的链长
top[i]:i所在长链的顶点
hb[i]:i的highbit highbithighbit值
twi[i]:2^i
 预处理：
对于highbit(x) 选择你喜欢的方法做。
对于tmp，用两个动态数组维护，存每条长链的顶点的向上len
向下len的祖先和儿子
（对于每条长链，存链中的节点显然无意义，因为你可以在询问时先跳到top）。
深搜：
一共dfs两遍
dfs1:预处理一些关于树的常规信息，如深度、长儿子
dfs2:处理链长和长链顶点
原文链接：https://blog.csdn.net/hzq_oi/article/details/88595343
*/
#include<bits/stdc++.h>
#define N 300005
using namespace std;
inline int rd()
{
int data=0,w=1;static char ch=0;
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(isdigit(ch))data=(data<<1)+(data<<3)+ch-'0',ch=getchar();
return data*w;
}
int first[N],cnt;
struct node
{int v,nxt;}
e[N<<1];
inline void add(int u,int v)
{
e[++cnt].v=v;
e[cnt].nxt=first[u];
first[u]=cnt;
}
int n,m,ans;
int f[N][20],d[N],dep[N],len[N],top[N],son[N],hb[N],twi[30];
void dfs1(int u,int fa) //根的深度为1
{
d[u]=dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int register i=1;i<=19;i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int register i=first[u];i;i=e[i].nxt)
{
int register v=e[i].v;
if(v==fa)continue;
dfs1(v,u);
if(d[u]<d[v]) //找出重儿子
{
d[u]=d[v];
son[u]=v;
}
}
}
void dfs2(int u,int fa)
{
len[u]=d[u]-dep[top[u]]+1;
if(!son[u])return;
top[son[u]]=top[u];
dfs2(son[u],u);
for(int register i=first[u];i;i=e[i].nxt)
    if(e[i].v!=son[u]&&e[i].v!=fa)
       top[e[i].v]=e[i].v,dfs2(e[i].v,u);
}
vector<int>up[N],down[N];
inline int query(int x,int k)//求k级祖先
{
if(k>=dep[x])return 0;
if(!k)return x;
x=f[x][hb[k]];//hb[k]代表k这个数字的最高位是2的多少次方
k^=twi[hb[k]];
if(!k)return x;
int register tmp=dep[x]-dep[top[x]];
if(tmp==k)
return top[x];
else
     if(tmp<k)return
     up[top[x]][k-tmp-1];
//x在某条轻链上，跳到top点后，还不够，不要向上跳
 else
      return down[top[x]][tmp-k-1];
//x在重链上，跳到top点后，跳过头了，所以还要向下移动下
}
int main()
{
n=rd();
for(int register i=1;i<n;i++)
{int register x=rd(),y=rd();add(x,y);add(y,x);}
dfs1(1,0);
top[1]=1;
dfs2(1,0);for(int  i=1;i<=n;i++)
{
if(i!=top[i])   continue;
//找出每条重链的顶点
int register tmp=0,prv=i;
while(tmp<len[i]&&prv)
{
 prv=f[prv][0],up[i].push_back(prv),tmp++;
}
tmp=0;prv=i;
while(tmp<len[i])
{
prv=son[prv],down[i].push_back(prv),tmp++;
//向下跳，跳到它的重儿子 }
}
twi[0]=1;
for(int register i=1;i<=20;i++)
twi[i]=twi[i-1]<<1;
for(int register i=1;i<=n;i++)
for(int register j=20;j>=0;j--)
if(twi[j]&i)
{
hb[i]=j;
    //对于数字i来说，它转成2进制后最高位是2^j
//例如7的最高位是2^2,8的是2^3
break;
}
m=rd();
while(m--)
{
int register x=rd(),k=rd();
x^=ans;
k^=ans;
ans=query(x,k);
printf("%d\n",ans);
}
return 0;
}