Hard problem

Revision en3, by Muaath_5, 2023-03-28 16:58:36

Recently, I solved 342E - Xenia and Tree using Sqrt decomposition.

The problem have two types of queries: - Color node $$$x$$$ red - Find minimum distance to any red color

I thought, what will be the solution if there is query: Color node $$$x$$$ blue.

I'm not sure if this is solvable using centroid decomposition, but is there another way?

Tags centroid decomposition, sqrt decomposition, problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Muaath_5 2023-03-28 16:59:18 4 Tiny change: 'queries:\n- Color ' -> 'queries:\n\n- Color ' (published)
en3 English Muaath_5 2023-03-28 16:58:36 32
en2 English Muaath_5 2023-03-28 16:57:13 330
en1 English Muaath_5 2023-03-28 16:52:08 46 Initial revision (saved to drafts)