专栏文章

[图论/数据结构] 一种重链剖分的扩展

FFelix72
算法·理论参与者 6已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@miodfde5
此快照首次捕获于
2025/12/02 17:23
3 个月前
此快照最后确认于
2025/12/02 17:23
3 个月前
查看原文
这里记录一种可以以 O(klog⁡2n)O(k\log^2n) 时间复杂度（单次询问），O(nk)O(nk) 空间复杂度实现 d(≤k)d(\leq k) 级邻域加，子树加，链加，以及对应求和的重链剖分方式。
先对该树进行一次正常的重链剖分，然后对其进行两轮 DFS。
第一轮 DFS 伪代码如下：
TXT
对当前点 u 进行 BFS；
对于每个儿子 v:
  递归进入 v;
第二轮 DFS 伪代码如下：
TXT
若当前点 u 还没有 dfn 标号，则给 u 的 dfn 标号 ++idx;
递归进入重儿子;
对于其他儿子 v:
  递归进入 v;
第一轮 DFS 中提到的特殊 BFS 伪代码如下：
TXT
将起点 s 加入队列;
当队列非空:
  取出队首节点 u;
  如果 u 是其所在重链的前 k 个点之一，且 u 还没有 dfn 标号:
    给 u 的 dfn 编号 ++idx;
  若 u 到 s 的距离小于 d:
    遍历 u 的所有儿子，将它们加入队列
上面的流程实际上做了这样的事情：
我们把树上的所有点分为两类，规定每条重链上的前 kk 个点为 AA 类点，剩下的都是 BB 类点。我们可以发现在刚才的流程中，第一轮 DFS 是在给 AA 类点标号，第二轮则是在给 BB 类点标号。最终的结果就是，AA 类点的 dfndfn 形成了一个“类 BFS 序状物”，BB 类点的 dfndfn 形成了一个“类树剖状物”，且 AA 类点AA 类点的 dfndfn 都小于 BB 类点。
我们可以用这个 dfndfn 序以单次 O(klog⁡2n)O(k\log^2n) 的时间复杂度做很多种操作。以下逐一讲解：

路径修改

可以发现 BB 类点的 dfndfn 遵循传统的树链剖分规律，因此我们可以按照经典的方式维护路径修改，并对途中每条重链的前 kk 个点单点修改。

dd 级邻域修改

这个问题可以转化成多次对一个点所有 r 级儿子的修改操作。因为 r≤d≤kr \leq d \leq k，因此 rr 级儿子中最多只有一个点是 BB 类点，剩下的都是 AA 类点，它们的 dfndfn 序遵循 BFS 序规律，是连续的，可以在数据结构上区间修改。处理完后再对单独的 AA 类点单点修改即可。

子树修改

先对一个点的 [0,k][0, k] 级儿子做 k+1k + 1 次上面的单层修改，然后我们可以发现，子树中剩下的节点有些是 AA 类点，有些是 BB 类点，但是同类点的 dfndfn 编号都是连续的。因此再做两次区间修改即可。
查询操作是类似的。这样，我们便得到了可以处理 kk 级邻域的重链剖分。
下面是一个粗糙的实现：
CPP
/* K_crane x N_Cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 100010, D = 110, mod = 998244353;
int Type, n, m, d; vector < int > tr[N]; long long org[N];

int rt, idx;
struct Line {long long k, b;};
Line operator * (Line u, Line v) {return {u.k * v.k % mod, (v.k * u.b + v.b) % mod};}
struct SGT
{
	int ls, rs; Line data, tag;
	#define ls(x) tree[x].ls
	#define rs(x) tree[x].rs
	#define data(x) tree[x].data
	#define tag(x) tree[x].tag
} tree[N * 2];
inline void push_tag(int now, Line _tag)
{data(now) = data(now) * _tag, tag(now) = tag(now) * _tag;}
inline void pushdown(int now)
{
	push_tag(ls(now), tag(now));
	push_tag(rs(now), tag(now));
	tag(now) = {1, 0};
}
inline void build(int &now, int l, int r)
{
	now = ++idx;
	data(now) = tag(now) = {1, 0};
	if(l == r) return ; int mid = (l + r) >> 1;
	build(ls(now), l, mid), build(rs(now), mid + 1, r);
}
inline void modify(int now, int l, int r, int L, int R, Line dt)
{
	if(L <= l && r <= R) {push_tag(now, dt); return ;}
	pushdown(now); int mid = (l + r) >> 1;
	if(L <= mid) modify(ls(now), l, mid, L, R, dt);
	if(mid < R) modify(rs(now), mid + 1, r, L, R, dt);
}
inline Line query(int now, int l, int r, int pos)
{
	if(l == r) return data(now);
	pushdown(now); int mid = (l + r) >> 1;
	if(pos <= mid) return query(ls(now), l, mid, pos);
	else return query(rs(now), mid + 1, r, pos);
}

int dep[N], siz[N], son[N], fa[N][22], top[N], len[N];
int dfn[N], rnk[N], df_sign, id[N][D], sum[N][D], min_id[N][D], nxt[N][D];
int tpA[N][D], tpB[N][D], far_tpA[N], far_tpB[N], Aid[N][D], Bid[N][D], far_Aid[N], far_Bid[N];
inline void init_A(int pos, int prt)
{
	sum[pos][0] = 1;
	dep[pos] = dep[prt] + 1, siz[pos] = 1, fa[pos][0] = prt;
	for(int i = 1; ; ++i)
	{
		if(fa[fa[pos][i - 1]][i - 1]) fa[pos][i] = fa[fa[pos][i - 1]][i - 1];
		else break;
	}
	for(int to : tr[pos])
	{
		if(to == prt) continue;
		init_A(to, pos), siz[pos] += siz[to];
		if(siz[to] > siz[son[pos]]) son[pos] = to;
		for(int i = 1; i <= d; ++i) sum[pos][i] += sum[to][i - 1];
	}
}
queue < int > q;
inline void bfs(int st, bool spe = false)
{
	q.push(st);
	while(!q.empty())
	{
		int pos = q.front(); q.pop();
		if(dep[pos] - dep[top[pos]] <= d)
		{
			if(!dfn[pos]) dfn[pos] = ++df_sign, rnk[df_sign] = pos;
			if(!id[st][dep[pos] - dep[st]]) id[st][dep[pos] - dep[st]] = dfn[pos];
		}
		if(dep[pos] - dep[st] == d) continue;
		for(int to : tr[pos])
		{
			if(to == fa[pos][0]) continue;
			q.push(to);
		}
	}
}
inline void init_B(int pos, int belong)
{
	nxt[pos][0] = pos;
	for(int i = 1; i <= d; ++i) nxt[pos][i] = son[nxt[pos][i - 1]];
	top[pos] = belong;
	if(son[pos]) init_B(son[pos], belong);
	len[pos] = len[son[pos]] + 1;
	for(int to : tr[pos])
	{
		if(to == fa[pos][0] || to == son[pos]) continue;
		init_B(to, to);
	}
}
inline void init_C(int pos)
{
	bfs(pos);
	for(int to : tr[pos])
	{
		if(to == fa[pos][0]) continue;
		init_C(to);
	}
}
inline void init_D(int pos)
{
	if(!dfn[pos]) dfn[pos] = ++df_sign, rnk[df_sign] = pos;
	if(son[pos]) init_D(son[pos]);
	for(int to : tr[pos])
	{
		if(to == fa[pos][0] || to == son[pos]) continue;
		init_D(to); 
	}
}
inline void init_E(int pos)
{
	if(dep[pos] - dep[top[pos]] <= d) ++tpA[pos][0], Aid[pos][0] = dfn[pos];
	else ++tpB[pos][0], Bid[pos][0] = dfn[pos];
	min_id[pos][0] = dfn[pos];
	for(int to : tr[pos])
	{
		if(to == fa[pos][0]) continue;
		init_E(to);
		if(far_Aid[to])
		{
			if(!far_Aid[pos]) far_Aid[pos] = far_Aid[to];
			else far_Aid[pos] = min(far_Aid[pos], far_Aid[to]);
		}
		if(far_Bid[to])
		{
			if(!far_Bid[pos]) far_Bid[pos] = far_Bid[to];
			else far_Bid[pos] = min(far_Bid[pos], far_Bid[to]);
		}
		far_tpA[pos] += far_tpA[to];
		far_tpB[pos] += far_tpB[to];
		for(int i = 1; i <= d + 1; ++i)
		{
			if(min_id[to][i - 1])
			{
				if(!min_id[pos][i]) min_id[pos][i] = min_id[to][i - 1];
				else min_id[pos][i] = min(min_id[pos][i], min_id[to][i - 1]);
			}
			if(Aid[to][i - 1])
			{
				if(!Aid[pos][i]) Aid[pos][i] = Aid[to][i - 1];
				else Aid[pos][i] = min(Aid[pos][i], Aid[to][i - 1]);
			}
			if(Bid[to][i - 1])
			{
				if(!Bid[pos][i]) Bid[pos][i] = Bid[to][i - 1];
				else Bid[pos][i] = min(Bid[pos][i], Bid[to][i - 1]);
			}
			tpA[pos][i] += tpA[to][i - 1];
			tpB[pos][i] += tpB[to][i - 1];
		}
		if(Aid[pos][d + 1])
		{
			if(!far_Aid[pos]) far_Aid[pos] = Aid[pos][d + 1];
			else far_Aid[pos] = min(far_Aid[pos], Aid[pos][d + 1]);
		}
		if(Bid[pos][d + 1])
		{
			if(!far_Bid[pos]) far_Bid[pos] = Bid[pos][d + 1];
			else far_Bid[pos] = min(far_Bid[pos], Bid[pos][d + 1]);
		}
	}
	far_tpA[pos] += tpA[pos][d + 1];
	far_tpB[pos] += tpB[pos][d + 1];
}

inline void work_b(int p, int k, Line cur, bool spe = true)
{
//	cerr << "B " << p << " " << k << '\n';
	if(k < 0) return ;
	if(!sum[p][k]) return ;
	if(nxt[p][k] && dep[nxt[p][k]] - dep[top[nxt[p][k]]] > d)
	{
		modify(rt, 1, n, dfn[nxt[p][k]], dfn[nxt[p][k]], cur);
		if(sum[p][k] > 1) modify(rt, 1, n, min_id[p][k], min_id[p][k] + (sum[p][k] - 1) - 1, cur);
	}
	else modify(rt, 1, n, min_id[p][k], min_id[p][k] + sum[p][k] - 1, cur);
}
inline void work_d(int tp, int bt, Line cur)
{
//	cerr << "D " << tp << " " << bt << '\n';
	while(tp != bt && dep[tp] - dep[top[bt]] <= d)
	{
		modify(rt, 1, n, dfn[tp], dfn[tp], cur);
		tp = son[tp];
	}
	modify(rt, 1, n, dfn[tp], dfn[bt], cur);
}

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> Type;
	cin >> n >> m >> d;
	for(int i = 1, x, y; i < n; ++i)
	{
		cin >> x >> y;
		tr[x].push_back(y);
		tr[y].push_back(x);
	}
	for(int i = 1; i <= n; ++i) cin >> org[i];
	init_A(1, 0), init_B(1, 1), init_C(1), init_D(1), init_E(1);
	build(rt, 1, n);
//	cerr << "dfn "; for(int i = 1; i <= n; ++i) cerr << dfn[i] << " "; cerr << '\n';
	for(int t = 1; t <= m; ++t)
	{
		int opt; cin >> opt;
		if(opt == 1)
		{
			int p; cin >> p;
			Line cur = query(rt, 1, n, dfn[p]);
			cout << (org[p] * cur.k + cur.b) % mod << '\n';
		}
		else if(opt == 2)
		{
			int p, dist; Line cur;
			cin >> p >> dist >> cur.k >> cur.b;
			for(int i = 0; i <= dist; ++i)
			{
				if(p >= 1) work_b(p, dist - i, cur), work_b(p, dist - i - 1, cur);
				else work_b(1, dist - i + p - 1, cur), work_b(1, dist - i + p - 2, cur);
				if(p > 1) p = fa[p][0]; else --p;
			}
		}
		else if(opt == 3)
		{
			int p; Line cur;
			cin >> p >> cur.k >> cur.b;
			for(int i = 0; i <= d; ++i) work_b(p, i, cur);
			if(far_tpA[p]) modify(rt, 1, n, far_Aid[p], far_Aid[p] + far_tpA[p] - 1, cur);
			if(far_tpB[p]) modify(rt, 1, n, far_Bid[p], far_Bid[p] + far_tpB[p] - 1, cur);
		}
		else if(opt == 4)
		{
			int x, y; Line cur;
			cin >> x >> y >> cur.k >> cur.b;
			while(top[x] != top[y])
			{
				if(dep[top[x]] < dep[top[y]]) swap(x, y);
				work_d(top[x], x, cur);
				x = fa[top[x]][0];
			}
			if(dep[x] < dep[y]) swap(x, y);
			work_d(y, x, cur);
		}
	}
	return 0;
}
/*
0
23 2 1
1 2
2 3
1 4
3 5
3 6
5 7
7 8
6 9
5 10
5 11
6 12
10 13
8 14
5 15
8 16
10 17
16 18
10 19
7 20
11 21
13 22
16 23
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
3 3 1 6
1 3
*/

评论

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

正在加载评论...