Top Tree
stripe_python · · 算法·理论
- 定义树
T 上的簇C=(V,E,B) ,其中(V,E) 为T 上的子连通块,B \subseteq V 且|B| \le 2 。满足\forall (u,v) \in E(T) \land u \in V \land v \notin V, u \in B 。
用人话来说,簇是
- 若
|B|=2 ,对u,v \in B 将u,v 称作C 的界点,u \to v 的路径称作C 的簇路径。
下面展示了一个簇的结构:
将树
-
对簇
C_1,C_2 满足|B(C_1) \cap B(C_2)|=1 ,定义簇的两种运算:- Rake
V=V(C_1) \cup V(C_2) ,E=E(C_1) \cup E(C_2) ,\textcolor{red}{B=B(C_1)} 。 - Compress
V=V(C_1) \cup V(C_2) ,E=E(C_1) \cup E(C_2) ,\textcolor{red}{B=(B(C_1) \setminus \{u\}) \cup (B(C_2) \setminus \{u\})} 。
运算要求封闭性,即
C=(V,E,B) 必须仍满足簇的定义。 - Rake
我们画图理解两种运算:
- 基簇:树边
(u,v)\in E(T) ,令V=\{u,v\} ,E=\{(u,v)\} ,B=\{u,v\} 。 - 根簇:
V=V(T) ,E=E(T) 。
初始时,我们有
对静态的
一般地,我们希望 STT 的树高较小。
-
对
T 进行重链剖分。对u_1 \to u_2 \to \cdots \to u_k 的一条重链:- 遍历
u_i ,递归u_i 的所有轻儿子v ,将v 子树收缩到(u_i,v) 。 - 将
u_i 的所有轻儿子对应的簇,使用 Rake 操作合并。
上述操作结束后,对
u_1 \sim u_k 对应的簇,使用 Compress 操作合并。 - 遍历
直接使用分治合并,树高是
- 按序列的带权中点进行分治,树高是
O(\log |V|) 的。
这句话的意义是,我们记录每个簇的实际
代码
个人认为比较清晰的一份实现。
enum node_type {RAKE, COMPRESS};
struct node {
node_type type; // 节点类型
node *l, *r, *f; // 左儿子 / 右儿子 / 父亲
int sz, u, v; // 簇的大小 / 上界点 / 下界点
// 其他可合并信息
node();
void pushup();
};
node* merge(node* x, node* y, node_type type) {
node* z = new node;
z->type = type, z->l = x, z->r = y, z->sz = x->sz + y->sz;
x->f = z, y->f = z;
if (type == RAKE) z->u = x->u, z->v = x->v;
else z->u = x->u, z->v = y->v;
return z->pushup(), z;
}
int fa[N], sz[N], son[N], len[N];
void dfs1(int u) { // 重链剖分
sz[u] = 1, son[u] = 0;
for (int v : e[u]) {
if (v == fa[u]) continue;
fa[v] = u, dfs1(v), sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
len[u] = len[son[u]] + 1;
}
node* build(node** a, int* pre, int l, int r, node_type type) { // 带权分治
if (l == r) return a[l];
int sum = pre[r] - pre[l - 1];
int mid = partition_point(pre + l, pre + r + 1, [&](int x) -> bool {
return 2 * (x - pre[l - 1]) <= sum;
}) - pre;
if (mid == r) mid--;
return merge(build(a, pre, l, mid, type), build(a, pre, mid + 1, r, type), type);
}
node* T[N];
node* dfs2(int u) { // 建 u 子树 STT
node** carr = new node*[len[u] + 5]; // Compress 重链
int* cpre = new int[len[u] + 5]; // Compress 前缀和
cpre[0] = 0; int tot = 0;
for (; u; u = son[u]) {
T[u] = new node; T[u]->u = fa[u], T[u]->v = u, T[u]->sz = 1;
node** rarr = new node*[e[u].size() + 5]; // Rake 轻儿子
int* rpre = new int[e[u].size() + 5]; // Rake 前缀和
rarr[1] = T[u], rpre[0] = 0; int cnt = 1;
for (int v : e[u])
if (v != fa[u] && v != son[u]) rarr[++cnt] = dfs2(v);
for (int i = 1; i <= cnt; i++) rpre[i] = rpre[i - 1] + rarr[i]->sz;
carr[++tot] = build(rarr, rpre, 1, cnt, RAKE);
}
for (int i = 1; i <= tot; i++) cpre[i] = cpre[i - 1] + carr[i]->sz;
return build(carr, cpre, 1, tot, COMPRESS);
}
应用
STT 之于树,就如同线段树之于序列,因此 STT 能维护很多奇特信息。
动态直径
问题 1 给定树
对簇
在 pushup 时,分 Rake 节点和 Compress 节点进行讨论,处理直径是否跨过界点。
可以发现半群信息的设计类似于线段树维护最大子段和。复杂度
动态 DP
比较奇妙的半群信息。下面以动态最大权独立集为例。
问题 2 给定树
对簇
为了避免算重,我们钦定选择上界点时,
合并信息时,在界点处进行讨论:
- 对 Rake 节点,
f_{x,y} \gets f_{x,y}(C_1) + f_{x,z}(C_2), z \in \{0,1\} 。 - 对 Compress 节点,
f_{x,y} \gets f_{x,z} (C_1)+f_{z,y}(C_2), z\in \{0,1\} 。
复杂度
链 / 子树修改查询
问题 3(P3384) 维护树
对簇