专栏文章

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

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

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@min01m0y
此快照首次捕获于
2025/12/01 18:21
3 个月前
此快照最后确认于
2025/12/01 18:21
3 个月前
查看原文

题目大意:

给定一棵树,一开始我们位于 mm 点。之后有 kk 次询问,每次我们可以走 tt 步,沿着唯一路径前往 dd 点,能到则到,不能到则尽量走。

知识点:树剖求树上 KK 级祖先

默认都会树上 KK 级祖先,如果不会请先学习【模板】树上 K 级祖先

思路:

很板的树上 KK 级祖先模板题。
对于每次询问我们先求出到 dd 点的路径长度 distdist
CPP
lca = LCA(x, d);
		
dist = h[x] + h[d] - 2 * h[lca];
//h数组是以1为根时,每个节点的深度
然后我们进行分类讨论:
  • 可以直接走到 dd 点时,我们修改位置到 dd
CPP
if (dist <= t) x = d;
  • 不能到达 lcalca 点时,我们修改位置到 xxtt 级祖先。
CPP
if (h[x] - h[lca] >= t) x = query(x, t);
//query求的是树上k级祖先
  • 可以到达 lcalca 点但不能到达 dd 点时,相当于求 dd 点的 disttdist - t 级祖先。
CPP
if (h[x] - h[lca] < t) x = query(d, dis - t);

代码

CPP
//码风一般,见谅qwq
//代码中写的是长链剖分
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int fa[N];
int h[N];
int maxh[N];
int deep[N];
int top[N];
int id[N];
int have[N];
vector<int> l[N];

int n, m, k;
int root;
int tot;

void dfs1(int u, int father, int high){
	fa[u] = father;
	h[u]  = high;
	maxh[u] = high;
	
	for (auto v : l[u]){
		if (v == fa[u]) continue;
		
		dfs1(v, u, high + 1);
		
		maxh[u] = max(maxh[u], maxh[v]);
		
		if (maxh[v] > maxh[deep[u]]) deep[u] = v;
	}
	
	return;
}

void dfs2(int u, int Top){
	++tot;
	
	top[u] = Top;
	id[u]  = tot;
	have[tot] = u;
			
	if (deep[u] == 0) return;
	
	dfs2(deep[u], Top);
	
	for (auto v : l[u]){
		if (v == fa[u] || v == deep[u])  continue;
		
		dfs2(v, v);
	}

	return;
}

int LCA(int x, int y){
	while (top[x] != top[y]){
		if (h[top[x]] < h[top[y]]) swap(x, y);
		
		x = fa[top[x]];
	}
	
	if (h[y] < h[x]) return y;
	
	return x;
}

int query(int u, int father){
	while (h[u] - h[top[u]] < father){
		father -= h[u] - h[top[u]];
		
		father -= 1;
		
		u = fa[top[u]];
	}
	
	int v = have[id[u] - father];
	
	return v;	
}

namespace IO{
	inline int read(){
		int x = 0, f = 1;
		char c = getchar();
		
		while(c < '0' || c > '9'){
			if (c == '-') f = -1;
			
			c = getchar();
		}
		
		while(c >= '0' && c <= '9'){
			x *= 10;
			x += c - '0';
			
			c = getchar();
		}
		
		return x * f;
	}
	
	void write(int x){
		if (x < 0){
			putchar('-');
			x = -x;
		}
		
		if (x < 10){
			putchar(x + '0');
			return;
		}
		else{
			write(x / 10);
			
			putchar(x % 10 + '0');
			
			return;
		}
	}
}

signed main(){
	n = IO::read();
	m = IO::read();
	k = IO::read();
	
	for (int i = 1; i < n; i++){
		int u, v;
		u = IO::read();
		v = IO::read();
		
		l[u].push_back(v);
		l[v].push_back(u);
	}
	
	root = 1;
	
	dfs1(root, 0, 1);
	
	dfs2(root, root);

	int x = m;	
	while(k--){
		int d, t;
		d = IO::read();
		t = IO::read();
		
		int lca = LCA(x, d);
		
		int dist = h[x] + h[d] - 2 * h[lca];
		
		if (dis <= t) x = d;
		else{
			if (h[x] - h[lca] >= t) x = query(x, t);
			
			else if (h[x] - h[lca] < t) x = query(d, dis - t);
		}
		
		IO::write(x);
		putchar(' ');		
	}

	return 0;
}

评论

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

正在加载评论...