Editorial for Mock CCC '18 Contest 2 S4 - A Tree Problem - Olympiads Online Judge

Editorial for Mock CCC '18 Contest 2 S4 - A Tree Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Imagine that there is a vertex $v$ $v$ incident on vertices $u_1$ $u_{1}$ and $u_2$ $u_{2}$ such that the two edges are the same color. The two subtrees of $u_1$ $u_{1}$ and $u_2$ $u_{2}$ assuming the tree is rooted at $v$ $v$ do not contain any good nodes.

If we check this for every pair of edges that have the same color, this gives us an $\mathcal O(N^2)$ $O (N^{2})$ solution.

We can improve this to linear-time by, instead of explicitly marking the nodes, keeping track implicitly of which subtrees are ineligible, and then DFSing in both directions to propagate which subtrees are blocked.

Comments

-1

Hadilo commented on Feb. 8, 2018, 4:57 a.m. ← edited →

Hot to "DFSing in both directions to propagate which subtrees are blocked" in $\mathcal{O}(N)$ $O (N)$ .