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)$ ~\mathcal 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)$ ~\mathcal{O}(N)~.