自动搬运

查看原文

来自洛谷，原作者为

	Zvelig1205 Q:3044754855 欢迎来吊打我

搬运于2025-08-24 22:35:16，当前版本为作者最后更新于2022-04-03 20:48:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

树剖求树上节点的 k 级祖先

题目传送门

闲话

我发现我有一个没 A 的蓝树剖

当树剖题做得比较多之后，简单的树剖还真能一眼出思路。

变量声明

• now：现在所处的节点位置。
• to：要到达的节点位置。
• reach：不能到达 to 时最后到达的节点。
• lca：now 和 to 的最近公共祖先。
• step：能走的步数。
• dis1：now 到 lca 的距离。
• dis2：to 到 lca 的距离。

思路

蒟蒻分类比较多（太菜，不会将情况合并）。

一、能到达

直接输出 to 并更新 now。

if(step>=dis1+dis2)wr(now=to),putchar(' ');

二、不能到达

蒟蒻怕错，将不能到达的情况又分成了两类：

• 向下跳

• 向上跳

1. 向下跳

此时，从上向下跳 step 步就相当于从下向上跳 dis2-step 步。

else if(lca==now)
{
	now=tiao(to,dis2-step);
	wr(now),putchar(' ');
}

2. 向上跳

还是为了防止出错，我又双叒叕分类了。

① 正巧跳到 lca：

直接输出 lca 并更新 now。

else if(dis1==step)wr(now=lca),putchar(' ');

② 在经过 lca 前不能走了：

now 向上跳 dis1 步。

else if(dis1>step)
{
	now=tiao(now,step);
	wr(now);putchar(' ');
}

③ 经过 lca 后停下：

总路程为 dis1+dis2，走过了 step，剩下了 dis1+dis2-step 步。to 向上跳 dis1+dis2-step 步。

else
{
	now=tiao(to,dis2-(step-dis1));
	wr(now);putchar(' ');
}

三、跳

思路中全是跳跳跳，那么到底怎么跳？

这题是什么？

对，树剖！

跳重链呗。

每次跳到重链的顶点的父节点，直到距离不够。

此时，当前节点和目标节点在一条重链上。

然后呢？

暴力跳？

树退化成链能让你当场去世

树剖有个美妙的性质，重链的时间戳是连续的。

而且深度也是连续的。

那么就有以下等式的推导：

$$\begin{array}{c} dep_{now}-dep_{to}=dfn_{now}-dfn_{to}\\ -dep_{now}+dep_{to}+dfn_{now}=dfn_{to}\\ k=dep_{to}-dep_{now}\\ dfn_{to}=dfn_{now}-k\\ to=rnk[dfn_{to}] \end{array}$$

所以代码就是这样：

int tiao(int x,int k)
{
	while(1)
	{
		if(dep[x]-dep[top[x]]+1>k)break;
		k-=dep[x]-dep[top[x]]+1;
		x=fa[top[x]];
	}
	return rnk[dfn[x]-k];
}

全代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=1e6+7;
int n,m;
int fir[inf],nex[inf<<1],poi[inf<<1],cnt;
void ins(int x,int y)
{
	nex[++cnt]=fir[x];
	poi[cnt]=y;
	fir[x]=cnt;
}
int fa[inf],dep[inf],siz[inf],son[inf];
void dfs1(int now,int from)
{
	siz[now]=1;fa[now]=from;
	dep[now]=dep[from]+1;
	for(int i=fir[now];i;i=nex[i])
	{
		int p=poi[i];
		if(p==from)continue;
		dfs1(p,now);
		siz[now]+=siz[p];
		if(siz[son[now]]<siz[p])
			son[now]=p;
	}
}
int top[inf],dfn[inf],rnk[inf],sum;
void dfs2(int now,int topn)
{
	top[now]=topn;
	dfn[now]=++sum;rnk[sum]=now;
	if(son[now]==0)return;
	dfs2(son[now],topn);
	for(int i=fir[now];i;i=nex[i])
	{
		int p=poi[i];
		if(p==fa[now]||p==son[now])
			continue;
		dfs2(p,p);
	}
}
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 now;
int tiao(int x,int k)
{
	while(1)
	{
		if(dep[x]-dep[top[x]]+1>k)break;
		k-=dep[x]-dep[top[x]]+1;
		x=fa[top[x]];
	}
	return rnk[dfn[x]-k];
}
int main()
{
	n=re();now=re();m=re();
	for(int i=1;i<n;i++)
	{
		int u=re(),v=re();
		ins(u,v),ins(v,u);
	}
	dfs1(1,1);dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		int to=re(),step=re();
		int lca=lca_(now,to);
		int dis1=dep[now]-dep[lca],dis2=dep[to]-dep[lca];
		if(step>=dis1+dis2)wr(now=to),putchar(' ');
		else if(lca==now)
		{
			now=tiao(to,dis2-step);
			wr(now),putchar(' ');
		}
		else if(dis1==step)wr(now=lca),putchar(' ');
		else if(dis1>step)
		{
			now=tiao(now,step);
			wr(now);putchar(' ');
		}
		else
		{
			now=tiao(to,dis2-(step-dis1));
			wr(now);putchar(' ');
		}
	}
    return 0;
}

广告

树剖相关知识

My blog