[NOI 2026] Rainbow Tree

The question

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

Algorithmic frontier

Reference frontier: $\mathcal{O}\!\left(n^{3}\right)$
Latest reported AI result: $\mathcal{O}\!\left(n^{2} \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(n^{2} \log^{2} n\right)$

AI / model: Not identified

Reported method

The page characterises feasibility by the minimum number of ancestor colours, giving a two-dimensional deficit DP A_u[k][r]; it writes the heavy-child transition as a polynomial multiplication plus a narrow-band correction and applies weight-balanced divide-and-conquer along each heavy path to avoid materialising every intermediate table, claiming O(n^2 log^2 n) time and O(n^2) space.

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 reports only local verification (samples, stress tests, ASan/UBSan) with no online-judge record, so the record stays at code_available.

Credits

Published by: __NikaidoHiro__

Independent reproduction: Not yet performed

Prior-art review: Not yet performed