GRAPART - EDITORIAL

general
, , , , ,
21

thanks though…

22

that is easy, Wf are the fathers of Rl, so wf<=Rl; Wo are the fathers of Ro and Rf, so Wo<=Ro+Rf

23 
Flips can be separately handled in separate DFS by maintaining a flipped array.

Actually, I think I can add something here.

What I did was, if answer was K=2, then do a simple DFS. In DFS, keeping assigning nodes one by one, first to U, then next to V, then next to U and so on.

I identified 4 cases, but they can be further reduced -

  • When the root of this fully colored subtree is in U and last colored leaf is also in U
  • When the root of this fully colored subtree is in V and last colored leaf is also in U
  • When the root of this fully colored subtree is in U and last colored leaf is also in V
  • When the root of this fully colored subtree is in V and last colored leaf is also in V

The intuition in cases was enough for me to give this approach a try. The proof I feel, is based on proving that the root node of subtree is connected either to its immediate next child, or to its grandchild (which in turn is connected its parent) in each of the 4 cases.

24

Here is a simpler and better solution.

2 Likes
25

This post is useful for my work, thanks