【BZOJ4281】[ONTAK2015]Związek Harcerstwa Bajtockiego
Description
给定一棵有n个点的无根树，相邻的点之间的距离为1，一开始你位于m点。之后你将依次收到k个指令，每个指令包含两个整数d和t，你需要沿着最短路在t步之内（包含t步）走到d点，如果不能走到，则停在最后到达的那个点。请在每个指令之后输出你所在的位置。
Input
第一行包含三个正整数n,m,k(1<=m<=n<=1000000,1<=k<=1000000)。
接下来n-1行，每行包含两个正整数x,y(1<=x,y<=n)，描述一条树边。
接下来k行，每行两个整数d,t(1<=d<=n,0<=t<=10^9)，描述一条指令。
Output
输出一行，包含k个正整数，即执行每条指令后你所在的位置。
Sample Input
3 1 2
1 2
2 3
3 4
1 1
1 2
2 3
3 4
1 1
Sample Output
3 2
题解：先倍增求出LCA，判断能否走到，然后倍增模拟走的过程即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1000010;
int n,m,S,mx,cnt;
int to[maxn<<1],next[maxn<<1],head[maxn],fa[21][maxn],dep[maxn]; inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x)
{
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa[0][x])
fa[0][to[i]]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);
}
int lca(int a,int b)
{
if(dep[a]<dep[b]) swap(a,b);
for(int i=mx;i>=0;i--) if(dep[fa[i][a]]>=dep[b]) a=fa[i][a];
if(a==b) return a;
for(int i=mx;i>=0;i--) if(fa[i][a]!=fa[i][b]) a=fa[i][a],b=fa[i][b];
return fa[0][a];
}
int find(int x,int y)
{
for(int i=mx;i>=0;i--) if(y&(1<<i)) x=fa[i][x];
return x;
}
int main()
{
n=rd(),S=rd(),m=rd();
int i,a,b,c;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),add(a,b),add(b,a);
dep[1]=1,dfs(1);
for(mx=1;(1<<mx)<=n;mx++)
for(i=1;i<=n;i++) fa[mx][i]=fa[mx-1][fa[mx-1][i]];
mx--;
for(i=1;i<=m;i++)
{
a=rd(),b=rd(),c=lca(S,a);
if(dep[S]+dep[a]-2*dep[c]<=b) S=a;
else
{
if(dep[S]-dep[c]>=b) S=find(S,b);
else S=find(a,dep[S]+dep[a]-2*dep[c]-b);
}
printf("%d",S);
if(i<m) printf(" ");
}
return 0;
}//3 1 2 1 2 2 3 3 4 1 1