[CSP-S 2019] Numbers on a Tree

The question

Can the source-listed reference complexity O(T n^2) be substantially improved?

Algorithmic frontier

Reference frontier: $\mathcal{O}\!\left(T n^{2}\right)$
Latest reported AI result: $\mathcal{O}\!\left(T n \log^{2} n\right)$

Normalized growth proxy · not benchmark data

This compares source-reported bounds; it is not a correctness or novelty finding.

Results

2026-09-12

Claimed result: $\mathcal{O}\!\left(T n \log^{2} n\right)$

AI / model: Not identified

Reported method

The page recasts the deletion order as a cyclic order of each vertex's ports, so the task becomes greedily minimising each label's successor; the second turn implements this with heavy-path decomposition, a segment tree composing min(c, pass?x:INF) functions and a DSU, and supplies a complete C++17 program claimed to run in O(n log^2 n) time and O(n) space per test case.

Verification

Source: Source reviewed
Theory: Theory not checked
Implementation: Code available
Prior art: Prior art not reviewed

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

The code is complete and matches the table's complexity, but the page carries no judge record and no stress-test report, so the record cannot be raised above code_available.

Credits

Published by: zzy_zzy

Independent reproduction: Not yet performed

Prior-art review: Not yet performed