专栏文章

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

ccold_jelly
P8025题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min01s21
此快照首次捕获于
2025/12/01 18:21
3 个月前
此快照最后确认于
2025/12/01 18:21
3 个月前
查看原文
听说 NOIP 考前写题解有助于 rp++。（划掉 (/▽＼)）
前置知识：树链剖分（重链剖分）、树剖求 LCA、树剖求 KK 级祖先。
不会也没关系哦，可以看看窝的博客啊（无耻地贴上链接）：树链剖分以及求 LCA、树上 KK 级祖先。可以帮忙点个赞赞吗 (/▽＼)。
会用到的记号：
  • LCA(x,y)\text{LCA}(x,y)：x,yx,y 的最近公共祖先；
  • depxdep_x：xx 的深度；
  • Dist(x,y)\text{Dist}(x,y)：x,yx,y 的距离（代表路径上的节点个数 −1-1）；
  • fa(x,K)fa(x,K)：xx 的 KK 级祖先。

题意简述

有一棵无根树，我们需要动态地维护一枚棋子在树上跳动的过程。单次跳动操作会给定目标节点 dd 与最大步数 tt，如果能在步数 tt 以内走到 dd，那么棋子就跳到 dd，否则棋子能跳多少是多少。

思路分析

既然这题是无根树，那我们首先随意钦定一个节点为根节点（比如我们这里就选择 11 号节点啦）。然后树剖一下，我们就能方便地求出 LCA 等信息了。
我们先分析分析题目，看看我们需要实现什么操作。
首先比较容易的是当点 mm 与 dd 之间的距离小于等于 tt 时，我们直接可以跳到 dd。
嗯嗯，那如果跳不到呢？我们肯定还是要在 mm 到 dd 的路径上跳的。这个时候我们就需要根据位置来分类讨论一下。
因为蒟蒻比较笨，这里分讨的稍微细了一点（有好好配图讲解哦）。
第一种情况，LCA(d,m)=d\text{LCA}(d,m)=d。这时候我们跳 tt 步即停止：
第二种情况，LCA(d,m)=m\text{LCA}(d,m)=m。这时候是恰好与第一种情况反过来的：
第三种情况，那么就是正常的 LCA 情况。我们将这个路径视为两段 m→LCA(d,m)m\to \text{LCA}(d,m)、LCA(d,m)→d\text{LCA}(d,m)\to d。根据分讨 tt 与 Dist(m,LCA(d,m))\text{Dist}(m,\text{LCA}(d,m)) 的大小关系，有：
综上所述，我们只用实现求 LCA、距离、K 级祖先啦 (●'◡'●)！

代码实现

鹅……这里蒟蒻在实现的时候实际上是把一开始 Dist(d,m)≤t\text{Dist}(d,m)\le t 的情况放在了三种情况里面了。单独拎出来也是可以的。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, k;
vector<int> e[N];
int dep[N], fa[N], siz[N], hs[N];
int top[N], id[N], ID[N], cnt;
void dfs1(int u, int father)//树剖 
{
	dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;
	int maxson = -1;
	for(auto i : e[u])
	{
		if(i == father) continue;
		dfs1(i, u);
		siz[u] += siz[i];
		if(maxson < siz[i]) maxson = siz[i], hs[u] = i;
	}
}
void dfs2(int u, int topf)
{
	top[u] = topf, id[u] = ++ cnt, ID[cnt] = u;
	if(hs[u] == 0) return;
	dfs2(hs[u], topf);
	for(auto i : e[u])
	{
		if(i == fa[u] || i == hs[u]) continue;
		dfs2(i, i);
	}
}
int LCA(int x, int y)//树剖求 LCA 
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
	if(dep[x] < dep[y]) return x;
	else return y;
}
int Dist(int x, int y, int lca)//求 Dist(x,y) 
{
	return dep[x] + dep[y] - 2 * dep[lca];
}
int faK(int x, int K)//求 fa(x,K) 
{
	while(id[x] - id[top[x]] + 1 <= K && x != 1)
	{
		K -= (id[x] - id[top[x]] + 1);
		x = fa[top[x]];
	}
	return ID[id[x] - K];
}
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i < n; i ++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	while(k --)
	{
		int d, t;
		scanf("%d%d", &d, &t);
		int lca = LCA(d, m);
		int dist = Dist(d, m, lca);
		if(lca == d)//情况一 
		{
			if(dist <= t) m = d;
			else m = faK(m, t);
		}
		else if(lca == m)//情况二 
		{
			if(dist <= t) m = d;
			else m = faK(d, dist - t);
		}
		else//情况三 
		{
			if(dist <= t) m = d;
			else
			{
				int D1 = dep[m] - dep[lca];
				int D2 = dep[d] - dep[lca];
				if(D1 <= t)
				{
					m = lca, t -= D1;
					m = faK(d, D2 - t);
				}
				else m = faK(m, t);
			}
		}
		printf("%d ", m);
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...