题解：P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego
ICU_midway_azuma
·
·
题解
挺好的一道树剖题。
首先我们思考我们会怎么走：
- 找到出发点和目标点的最近公共祖先（显然）；
- 向“上”（节点深度减少）从出发点走到最近公共祖先；
- 向“下”（节点深度增加）走到目标点。
（记出发点为 u，目标点为 v，两点的最近公共祖先为 w，i 和 j 之间的最短路长度为 dis_{i,j}）。
我们可以分类讨论：
-
如果剩余步数 step \ge dis_{u,v} ，直接更新所在位置即可。
-
如果 dis_{u,v} > step > dis_{u,w}，那么先将 step 减去 dis_{u,w}，再从 w 开始向下跳 step 步。
-
如果 dis_{u,w}\geq step，那么从 u 开始向上跳 step 步。
也就是说我们每次处理询问先分讨，然后有两种操作：
用树剖可以轻松实现。
向上跳的操作：每次检查当前所在的重链是否可以被完全跳过，如果可以，就跳，并将 step 减去对应的步数。如果不能，直接在重链中寻找对应位置即可。
int up(int x,int step){
while(step){//还有剩余步数
if(id[x]-id[top[x]]>=step){//如果不能跳过
x=tmp[id[x]-step];//这里做一下解释，树剖dfs2后会给每个节点一个标号，tmp[i]为标号为i的节点的最初序号
step=0;
break;
}
step-=id[x]-id[top[x]];//扣除步数
x=fa[top[x]];
step--;//注意从重链头跳到其父亲也算一步哦
}
return x;
}
向下跳不好直接实现，但我们换个思路：
单次询问复杂度 $O(\log n)$，可以通过此题。
代码：
```
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct node{
int v,w,next;
}edge[1000005<<1];
int a[1000005];
int head[1000005],num;
void add(int u,int v){
edge[++num].next=head[u];
head[u]=num;
edge[num].v=v;
}
int fa[1000005],dep[1000005],son[1000005],siz[1000005];
int id[1000005],tmp[1000005],top[1000005],cnt;
void dfs1(int now,int fath,int deep){
dep[now]=deep;
fa[now]=fath;
siz[now]=1;
int maxson=-1;
for(int i=head[now];i;i=edge[i].next){
int v=edge[i].v;
if(v==fath)continue;
dfs1(v,now,deep+1);
siz[now]+=siz[v];
if(maxson<siz[v]){
maxson=siz[v];
son[now]=v;
}
}
}
void dfs2(int now,int topf){
id[now]=++cnt;
tmp[cnt]=now;
top[now]=topf;
if(!son[now])return;
dfs2(son[now],topf);
for(int i=head[now];i;i=edge[i].next){
int v=edge[i].v;
if(v==fa[now]||v==son[now])continue;
dfs2(v,v);
}
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
return x;
}
int up(int x,int step){
while(step){
if(id[x]-id[top[x]]>=step){
x=tmp[id[x]-step];
step=0;
break;
}
step-=id[x]-id[top[x]];
x=fa[top[x]];
step--;
}
return x;
}
int d,t;
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs1(1,0,1);
dfs2(1,1);
while(k--){
scanf("%d%d",&d,&t);
int z=LCA(m,d);
if(dep[m]+dep[d]-dep[z]*2<=t){
m=d;
}
else if(dep[m]-dep[z]<=t){
t-=(dep[m]-dep[z]);
m=up(d,dep[d]-dep[z]-t);
}
else{
m=up(m,t);
}
printf("%d ",m);
}
return 0;
}
```