Top Trees 领先®

全局平衡二叉树

考虑这样一个问题：

有一棵 $n$ $n$ 个节点的树，需要支持两种操作：
- 给 $1\sim x$ 路径上每个节点权值 $+y$ ；
- 求 $1\sim x$ 路径上每个节点权值之和。

一个常见的解法是树链剖分+线段树。考虑有没有什么优化空间：

每次操作都是在同一条重链上的，我们对于每条重链开一棵线段树。
对于每棵线段树，我们希望比较“重”的节点深度更低一点，因为在到达这个节点之前我们付出了更大的代价。
具体地，我们称一个节点 $x$ 的重量为 $sz_x-sz_{hs_x}$ ，即轻儿子大小之和 $+1$ 。
我们分治建出这棵线段树：假设当前线段树节点代表的区间是 $[l,r]$ ，我们令 $mid$ 为第一个满足 $[l,mid]$ 总重量大于 $[l,r]$ 总重量的一半的位置。
这样我们从一个节点开始往上跳，经过 $\mathcal O(1)$ 个线段树节点，区间的总重量就会翻倍；而从一条重链跳到更上一层的重链的时候，这个区间总重量可以直接继承。由于只会翻倍 $\mathcal O(\log n)$ 次，总深度也只有 $\mathcal O(\log n)$ 。

这样我们就成功把这样的链操作问题优化到了

\mathcal O(\log n)

。

静态 Top Tree

注意到全局平衡二叉树并不是一棵二叉树，有没有办法变成一棵二叉树？

我们可以对每个节点的轻儿子同样建一棵“重量平衡”的线段树，拼在原树的对应部分（在实践中，可以把这个点到重儿子的边也视为一个大小为

1

的儿子），这样并不会改变最大深度

\mathcal O(\log n)

的性质。

我们可以观察一下这棵树的性质：

一个节点的管辖范围是原树上的一个连通块，每个叶子是一条边。
合并两个轻儿子对应的节点就是合并两个根相同的连通块；重链的线段树上的节点就是将一个连通块的一个叶子替换为另一个连通块。我们称两种合并操作为 rake 和 compress。
对于一个连通块，只有一个叶子可能在将来被 compress 操作替换掉。我们称连通块的根为上界点，这个叶子为下界点。这样 rake 操作就是 $(a,b)(a,c)\to(a,c)$ ，compress 操作就是 $(a,b)(b,c)\to(a,c)$ 。

这样对于一些复杂信息（如很多动态 DP 类问题），可以直接设计关于连通块和两个界点的状态（而不需要像传统做法一样考虑重链之间的影响等），像线段树一样直接合并；同时，类似线段树，也可以完成静态 Top Tree 合并等操作。

P4751 【模板】动态 DP（加强版）

题意：有一棵

n

个点的树，点有点权。

m

次操作，每次修改一个点的点权，询问最大权独立集的权值之和。

我们容易设计出这样的状态：

f_{u,0/1,0/1}

表示当前节点范围内，两个界点是否被选的最大权值和（不包含上界点的权值）。

rake 合并时：

f_{u,x,y}=\max\limits_{z\in\{0,1\}}f_{ls,x,z}+f_{rs,x,y}

。

compress 合并时：

f_{u,x,y}=\max\limits_{z\in\{0,1\}}f_{ls,x,z}+f_{rs,z,y}

。

完整代码

CPP

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

constexpr int N = 1e6 + 5, inf = 1e9;

int n, m;
vector<int> G[N];

using node = array<array<int, 2>, 2>;
node tr[N << 1];

node rake(const node &a, const node &b)
{
	node res{};
	for (auto x : {0, 1})
		for (auto y : {0, 1})
			res[x][y] = max(a[x][0], a[x][1]) + b[x][y];
	return res;
}
node compress(const node &a, const node &b)
{
	node res{};
	for (auto x : {0, 1})
		for (auto y : {0, 1})
			res[x][y] = max(a[x][0] + b[0][y], a[x][1] + b[1][y]);
	return res;
}

int ls[N << 1], rs[N << 1], fa[N << 1], tot;
bool typ[N << 1];
void pushup(int x)
{
	if (typ[x] == 0)
		tr[x] = rake(tr[ls[x]], tr[rs[x]]);
	else
		tr[x] = compress(tr[ls[x]], tr[rs[x]]);
}
int add(int u, int v, bool t)
{
	ls[++tot] = u, rs[tot] = v;
	fa[u] = fa[v] = tot, typ[tot] = t;
	pushup(tot);
	return tot;
}

// 树链剖分
int f[N], sz[N], hs[N];
void dfs1(int u, int fa)
{
	f[u] = fa, sz[u] = 1;
	for (auto v : G[u])
		if (v != fa)
		{
			dfs1(v, u), sz[u] += sz[v];
			if (sz[v] > sz[hs[u]])
				hs[u] = v;
		}
}

// 带权分治
using pii = pair<int, int>;
using vit = vector<pii>::iterator;
int dc(vit l, vit r, bool t)
{
	if (l + 1 == r)
		return l->first;
	int sum = 0;
	vit mid = l;
	for (vit x = l; x != r; ++x)
		sum += x->second;
	while (mid + 1 != r && sum > 0)
		sum -= mid->second << 1, ++mid;
	// 此处预处理前缀和后二分可以做到线性建树，但通常没有必要
	return add(dc(l, mid, t), dc(mid, r, t), t);
}

// 建树
// 需要注意会包含 u 的父亲到 u 的边
int dfs2(int u)
{
	vector<int> ch;
	// 提取重链
	int x = u;
	while (hs[x])
		ch.push_back(x), x = hs[x];
	vector<pii> rt{{u, 1}};
	for (auto x : ch)
	{
		vector<pii> vc;
		for (auto y : G[x])
			if (y != f[x] && y != hs[x])
				vc.emplace_back(dfs2(y), sz[y]);
		vc.emplace_back(hs[x], 1);
		// 把轻子树 rake 到重链的一条边上
		// 需要注意 rake 也是有顺序的
		rt.emplace_back(dc(vc.begin(), vc.end(), 0), sz[x] - sz[hs[x]]);
	}
	return dc(rt.begin(), rt.end(), 1);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> tr[i][0][1], tr[i][1][1] = -inf;
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0);
	tot = n;
	// 注意直接调用 dfs2(1) 会包含 0->1 的边
	// 如果不需要，可以对 1 的每个儿子分别建树后带权分治合并
	int rt = dfs2(1);
	int lastans = 0;
	while (m--)
	{
		int x;
		cin >> x;
		x ^= lastans;
		cin >> tr[x][0][1];
		while (x = fa[x])
			pushup(x);
		cout << (lastans = max(tr[rt][0][0], tr[rt][0][1])) << '\n';
	}
}

设计状态的技巧

Top Tree 的信息合并方式对边信息更友好：两个连通块合并时，会有一个界点同时在两个连通块内，但边集无交。需要维护关于点的信息时，可以放到点到父亲的边上，即状态不包含上界点，并添加一条

0

到根的边。

设计关于路径的状态时，通常需要关注一下上界点的不包含下界点的子树相关的信息是否能被正确处理。

P9168 [省选联考 2023] 人员调度

直接给出删除一个人的反悔贪心需要支持的操作形式：

每个点有两个点权 $a_i,b_i$ ，满足每个子树 $\sum b_i\ge 0$ ；
需要支持单点修改，查询 $a_i$ 最大的 $i$ 满足对于每个 $i$ 的祖先 $x$ ，子树 $\sum b_x>0$ 。

我们特别关注一下两个界点之间的链：链上的点的子树

b_i

和还需要加上后续在右边 compress 的结点的

b_i

之和；不在链上的点子树

b_i

和已经确定。

考虑对于链上的点，如果最终子树

\sum b_i=0

，那他一定也是当前连通块内子树

\sum b_i

的最小值。

我们容易想到维护

mx_{0/1}

表示

a_i

最大的点

i

，

i

到上界点的路径上，不在界点之间的路径上的点全都合法，在界点之间的路径上的部分包含/不包含

\sum b_i

的最小值。同时维护这个最小值本身和整个连通块的

\sum b_i

就能完成合并。

于是我们成功把这个题爆标了。

YDRG007E. 广义串并联图上邻域数点

题意：有

n

个集合，设

f(S,x,y)

为

x\sim y

路径上在

S

内的点权之和减去不在

S

内的点权之和。需要支持合并两个集合，求某个集合的

\sum\limits_{x,y\in S}f(S,x,y)

。

我们考虑设计出能合并的信息，之后可以类比线段树合并完成静态 Top Tree 合并。

类似线段树维护子区间的方式，容易想到维护总和以及到上/下界点的点权和之和（不包含上界点的权值），以及这些对应的路径数。

但我们发现这是不够的。上界点不同子树之间的路径会经过上界点，上界点的权值在之后 compress 的时候才会被算到，所以我们需要记录这种路径的个数和下界点的权值。

同时，从上界点的不包含下界点的子树开始，经过上界点到达下界点继续往下走也是可能的，这样的路径的信息也需要记录。

文章操作

全局平衡二叉树

静态 Top Tree

设计状态的技巧

相关推荐

评论

Top Trees 领先®