所有指标均为确定性的算法步骤计数与随机树对拍断言(固定种子
20261121ULL),与时钟无关。
tree_dp.cpp:实现并交叉验证:- 两遍换根 DP(可逆的距离和、不可逆的前后缀
max单调半群最远距离)vs \(O(n^2)\) 暴力全源 BFS; - 虚树构造(按 DFS 序排序 + 右链单调栈 + LCA 补点,断言点数 \(\le 2k-1\))vs 原树线性统计;
- 树上背包:朴素 \(O(nm^2)\)、子树上界截断 \(O(nm)\)、后序 DFS 线性背包 \(O(nm)\) 的内层转移次数统计与一致校验;
- 点分治路径计数 vs \(O(n^2)\) 暴力全对最短路计数。
- 两遍换根 DP(可逆的距离和、不可逆的前后缀
plot_knapsack.py:由results/knapsack_ops.csv生成../knapsack-ops-plot.svg。- 运行方式:
bash run.sh源码下载
本文相关源码已整理,共 3 个文件。