Luogu · P5659

[CSP-S 2019] 树上的数

[CSP-S 2019] Numbers on a Tree

稳定 ID
luogu-p5659
问题状态
所报突破
主题
algorithms

问题

能否显著改进来源所列的 O(T n^2) 参考复杂度?

算法前沿

参考前沿
O ⁣(Tn2)\mathcal{O}\!\left(T n^{2}\right)
最新所报 AI 结果
O ⁣(Tnlog2n)\mathcal{O}\!\left(T n \log^{2} n\right)
归一化增长代理 · 非基准测量数据

此处比较的是来源所报复杂度,不构成正确性或原创性结论。

结果

2026-09-12

所报结果: O ⁣(Tnlog2n)\mathcal{O}\!\left(T n \log^{2} n\right)

AI / 模型: 未标明

所述方法

源页面先将操作顺序转为每个结点端口的环形排列,把问题变成按字典序依次最小化后继;第二轮用重链剖分、维护函数复合的线段树与并查集实现,并给出完整 C++17 代码,声称单组 O(n log^2 n) 时间、O(n) 空间。

核验

来源
来源已查阅
理论
理论未独立复核
实现
已有代码
前人工作
未检索前人工作

The result page was opened and compared with the collection claim. Legacy audit state: audited_public.

代码完整且直接对应表中复杂度,但源页面没有任何评测记录或本地对拍报告,因此不能升为 judge_verified。

署名与贡献

发布者
zzy_zzy

独立复现: 尚未进行

前人工作复核: 尚未进行

来源与历史

来源与历史

参与