题面

给定一棵树，每次询问一个点的\(k\)次祖先，强制在线。

Vijos

题解

长链剖分。

链接暂时咕咕咕了。

现在可以戳链接看题解了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 300300

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int hson[MAX],dep[MAX],md[MAX],len[MAX];

int p[MAX][20],top[MAX],n,hbit[MAX];

void dfs1(int u,int ff)

{

	md[u]=dep[u]=dep[ff]+1;p[u][0]=ff;

	for(int i=1;i<20;++i)

		if(p[u][i-1])p[u][i]=p[p[u][i-1]][i-1];

		else break;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		dfs1(v,u);

		if(md[v]>md[hson[u]])hson[u]=v,md[u]=md[v];

	}

}

void dfs2(int u,int tp)

{

	top[u]=tp;len[u]=md[u]-dep[top[u]]+1;

	if(hson[u])dfs2(hson[u],tp);

	for(int i=h[u];i;i=e[i].next)

		if(e[i].v!=p[u][0]&&e[i].v!=hson[u])

			dfs2(e[i].v,e[i].v);

}

vector<int> U[MAX],D[MAX];

int Query(int u,int k)

{

	if(k>dep[u])return 0;if(!k)return u;

	u=p[u][hbit[k]];k^=1<<hbit[k];

	if(!k)return u;

	if(dep[u]-dep[top[u]]==k)return top[u];

	if(dep[u]-dep[top[u]]>k)return D[top[u]][dep[u]-dep[top[u]]-k-1];

	return U[top[u]][k-dep[u]+dep[top[u]]-1];

}

int main()

{

	n=read();

	for(int i=1;i<n;++i)

	{

		int u=read(),v=read();

		Add(u,v);Add(v,u);

	}

	dfs1(1,0);dfs2(1,1);

	for(int i=1;i<=n;++i)

		if(i==top[i])

		{

			int l=0,x=i;

			while(l<len[i]&&x)x=p[x][0],++l,U[i].push_back(x);

			l=0,x=i;

			while(l<len[i])x=hson[x],++l,D[i].push_back(x);

		}

	int mx=1;

	for(int i=1;i<=n;++i)

	{

		if((i>>mx)&1)++mx;

		hbit[i]=mx-1;

	}

	int m=read(),ans=0;

	while(m--)

	{

		int u=read()^ans,v=read()^ans;

		printf("%d\n",ans=Query(u,v));

	}

	return 0;

}