并行树收缩

活跃树与摘要接口 ​

输入是一棵有根树公理库树Tree连通且无圈的无向图，等价地任意两点间有唯一简单路径。。算法维护由尚未收缩节点组成的活跃树，并让已删除部分的贡献以摘要附着在边或节点上。摘要组合必须满足问题所需的结合次序；若运算不交换，孩子顺序也属于状态。

Tree contraction 不是随意删节点。每个局部操作都要给出替代摘要，使将来在更小树上计算的结果，展开后等于原树结果。正确性通常由“收缩前后代表同一个边界函数”归纳证明。

Rake 与 compress ​

Rake 选择叶 $v$，把 $v$ 及其入边携带的贡献合入父节点，然后删除 $v$。同一父亲的多个叶若同时 rake，必须能按规定方式合并，或先选至多一个以避免写冲突。

Compress 选择只有一个活跃孩子的非根节点 $v$，把父边摘要与子边摘要复合成一条跨过 $v$ 的边，再删除 $v$。相邻的两个 unary 节点不能在同一原地轮都作为中心，否则会同时改同一边；通常在每条 unary path 上选独立集。

表达式树的状态轨迹 ​

考虑表达式 (a+b)*(c-d)。叶 a,b,c,d 先携带输入值；两个加减节点分别等待左右操作数。可以在一轮选择不冲突叶，把已知值 rake 到父节点的有序参数槽，两个参数齐全后父节点求出 a+b 或 c-d。

随后这两个子表达式值作为叶贡献 rake 到乘法根，根输出最终值。若先只收到 b，父摘要可表示一元函数 $x\mapsto x+b$；收到 a 后代入。对减法，左右槽不能交换，否则 c-d 会变成 d-c。

更一般的树 DP 可把被收缩部分表示为从边界状态到局部答案的函数；compress 对应函数复合，rake 对应把完成的侧支摘要并入主路径。

每轮常数比例缩小 ​

先把一般有序树二叉化，考虑节点按活跃孩子数分为叶、unary 和 branching。树中 branching 节点数小于叶数；因此若叶很多，可从叶中选一个无父冲突的常数比例执行 rake。

若叶不多，除去少量 branching 后，大量节点位于 unary paths。每条路径按奇偶位置选独立集，可 compress 至少常数比例的 unary 节点。于是每个 phase 能删除活跃节点的固定比例，活跃规模从 $n$ 降为 $\alpha n$（某个 $\alpha <1$），phase 数为 $O(\log n)$。

只写“叶和度二点很多”不够：选择集还必须保证局部写互斥，并证明二叉化增加的节点数仅为线性。不同 contraction 版本的常数和冲突规则可不同，但都要交付这两个证明。

Work 与 depth ​

若每个节点只在被删除时做常数摘要工作，总有 $O(n)$ 有效收缩 work，依赖层数为 $O(\log n)$。然而每个 phase 若重新扫描全部原数组寻找活跃节点，会产生 $O(n\log n)$ work。

Work-efficient 实现需要维护活跃邻接、候选队列，并并行选取独立操作集；随机 coin tossing 或确定性对称破缺也有自身成本。经典结论不能由“节点最终只删一次”自动推出，因为寻找下一批节点同样属于 work。

在Work–Depth 模型公理库Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。中，应分别声明 contraction 核心与候选选择的 $W,D$。若摘要组合本身需 $q$ 时间或空间，还要乘入每个局部操作。

与 scan 的联系 ​

Compress 在一条 unary path 上相当于对边函数做有序归约；若要恢复每个被删节点的上下文，可在路径上使用并行 scan公理库并行前缀扫描parallel prefix scan · parallel scan · prefix computation用上扫归约和下扫传播在线性工作、对数深度内计算任意幺半群运算的全部前缀。计算前缀与后缀复合。Rake 处理的是侧枝，scan 处理的是线性链，两者职责不同。

这也解释了结合律的重要性：不同 contraction 顺序必须得到同一摘要。没有结合律时，必须把原括号结构编码进摘要，而不能自由重排收缩。

实现与问题边界 ​

高阶节点若让所有孩子同时写父摘要，会产生 CRCW 风格冲突；可以先对子摘要做局部归约，或二叉化后只暴露常数度。删除节点后需原子更新父子关系，双缓冲 phase 可简化正确性但增加空间。

标准 PRAM 版本在明确的独立集选择与摘要常数时间前提下，可达到 $O(n)$ work、$O(\log n)$ depth；具体是确定性还是期望保证取决于选择算法。Tree contraction 求静态整树结果，不是支持 link/cut 的动态树结构。输出若要求每个节点答案而非根答案，还需记录收缩历史并 reverse expansion；只保留最终根摘要无法恢复全体结果。

参考资料

• Gary Miller, John Reif, Parallel Tree Contraction and Its Application, FOCS, 1985.
• Gary Miller, John Reif, Parallel Tree Contraction, Part 1: Fundamentals, Advances in Computing Research, 1989.
• Joseph JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.