数据结构 Trick 之：子树 k 距离内问题

能够解决的题目类型

这个 Trick 能解决的题目形如：

给定 $n$ 个节点的有根无边权有点权树。
有 $m$ 个询问，每个询问形如点 $x$ 的子树内与 $x$ 深度差不超过 $k$ 的点的极值/排名/和。
$O(n\,log\,n)$ 可过。

优缺点

优点：可以强制在线，代码简单。缺点：可能被卡常（概率非常小）。

思路

首先，深度差不超过

k

这个限制很难办，我们无法用一维的编号把这些点串起来，而且没有什么差分方法。

那么——二维，启动！

我们把一个数点

x

变成二维平面上的点：

(depp_x\,,dfn_x)

。那么对于一个点

p

的询问就变成了横坐标在

[depp_p\,,depp_p+k]

中，纵坐标在

[dfn_p\,,dfn_p+sz_p-1]

的点的极值/排名/和。

这个显然可以用树套树，但是

O(n\,log^2\,n)

，有没有更优的方法呢？

我们考虑主席树，但是主席树必须满足可减性，而最值没有。 但是，当一个点的横坐标在属于

[1,depp_p-1]

时，他的纵坐标一定不属于

[depp_p\,,dep_p+k]

，也就是说我们并不需要将两颗线段树相减，那么询问也就不用讲满足可减性。

所以我们就可以愉快地切题了。

算法流程

用一个 dfs 求出每个节点的 $dfn,sz,depp$ 。
把节点按照深度排序，一个一个加入主席树，并记录对于每个深度的最后一课主席树的根的下标 $idx$ 。

例题代码

本 Trick 的代码基本每道题没什么变化，直接套用就行了 CF893F Subtree Minimum Query

CPP

#include <bits/stdc++.h>
using namespace std;

#define midd ((node[u].l + node[u].r) >> 1)
constexpr int maxn = 100010;

int n, r, m, v[maxn], a, b, dfn[maxn], nowdfn, depp[maxn], s[maxn], idx[maxn], sz[maxn], lans, maxdep = 0;
vector <int> G[maxn];

struct nodee {
	int v, l, r, ls, rs;
} ;
struct tr {
	nodee node[maxn << 5];
	int root[maxn], cnt;
	void build(int &u, int l, int r) {
		u = ++cnt;
		node[u] = {1000000000, l, r, 0, 0};
		if (l == r) return ;
		build(node[u].ls, l, midd);
		build(node[u].rs, midd + 1, r);
		return ;
	}
	void update(int &u, int pree, int x, int k) {
		u = ++cnt;
		node[u] = node[pree];
		node[u].v = min(node[u].v, k);
		if (node[u].l == node[u].r) return ;
		if (x <= midd) update(node[u].ls, node[pree].ls, x, k);
		else update(node[u].rs, node[pree].rs, x, k);
		return ;
	}
	int query(int u, int l, int r) {
		if (node[u].l >= l && node[u].r <= r) return node[u].v;
		int ress = 1000000000;
		if (l <= midd) ress = min(query(node[u].ls, l, r), ress);
		if (r > midd) ress = min(query(node[u].rs, l, r), ress);
		return ress;
	}
} t;

void dfs(int u, int fa) {
	sz[u] = 1;
	dfn[u] = ++nowdfn;
	for (int now : G[u]) {
		if (now == fa) continue;
		depp[now] = depp[u] + 1;
		maxdep = max(maxdep, depp[now]);
		dfs(now, u);
		sz[u] += sz[now];
	}
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n >> r;
	depp[r] = 1;
	for (int i = 1; i <= n; i++) {
		s[i] = i;
		cin >> v[i];
	}
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(r, 0);
	sort(s + 1, s + 1 + n, [](int a, int b){return depp[a] < depp[b];});
	// 以上为第一部分 dfs
	t.build(t.root[0], 1, n);
	idx[0] = t.root[0];
	for (int i = 1; i <= n; i++) {
		t.update(t.root[i], t.root[i - 1], dfn[s[i]], v[s[i]]);
		if (depp[s[i]] != depp[s[i + 1]]) idx[depp[s[i]]] = i;
	}
	// 以上为第二部分 主席树预处理
	cin >> m;
	while (m--) {
		cin >> a >> b;
		a = (a + lans) % n + 1;
		b = (b + lans) % n;
		lans = t.query(t.root[idx[min(maxdep, depp[a] + b)]], dfn[a], dfn[a] + sz[a] - 1);
		cout << lans << '\n';
	}
	
	return 0;
}

数据结构 Trick 之：子树 k 距离内问题

文章操作

能够解决的题目类型

优缺点

思路

算法流程

例题代码

相关推荐

评论

数据结构 Trick 之：子树 k 距离内问题