题解：P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego

挺好的一道树剖题。

首先我们思考我们会怎么走：

找到出发点和目标点的最近公共祖先（显然）；
向“上”（节点深度减少）从出发点走到最近公共祖先；
向“下”（节点深度增加）走到目标点。

（记出发点为

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

减去对应的步数。如果不能，直接在重链中寻找对应位置即可。

CPP

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;
}

向下跳不好直接实现，但我们换个思路：

w

和

v

由一条链连接，长为

dis_{v,w}

，从

w

往

v

跳

step

步等价于从

v

往

w

跳

k-step

步。

单次询问复杂度

O(\log n)

，可以通过此题。

代码：

CPP

#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;
}

题解：P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego

文章操作

相关推荐

评论

题解：P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego