CustomCC0-1.0#ct-p6-032400
Centroid Nearest Active
Summary
- •Phase 6 / combined-techniques
- •Reasoning-first competitive programming drill
Problem Description
On tree, toggle active nodes and query minimum distance to active from node v. Your submission must justify algorithm choice, prove correctness, and test adversarial edge cases.
How to read this problem in plain language:
- This is a Phase 6 reasoning drill focused on combined-techniques.
- Typical lenses to test first: tree, centroid, data-structure.
- Constraints reminder: n,q <= 2e5
Mini examples for mental simulation:
1) Boundary example: Return -1 when set is empty. Explain expected behavior and why naive logic may fail.
2) Adversarial example: State should remain consistent. Explain expected behavior and why naive logic may fail.
Lite-mode writing target:
- Write 1~2 observations that shrink the search space.
- Name one final algorithm and state target complexity explicitly.
- Validate with at least 2 edge cases and one hand simulation.
Constraints
- •n,q <= 2e5
Analysis
Key Insight
Need deletion-aware structure, not single scalar.
treecentroiddata-structure