I'm having trouble solving QTREE4 using centroid decomposition.
I don't know if it can be solved with HLD or Sqrt Decomposition nor do I know anything about these algorithms.I need help(hints would be great) on how to approach this problem using only CD.
What's bugging me the most is that edges are weighted(weights can be negative).
I'm thinking every centroid should store as many distances/answers(an answer is a distance between this centroid and a white node) below it as the number of it's subtrees(it's outdegree) and itself if it's white.That's because if we store two distances of two nodes in a centroid when this centroid isn't their LCA, we can't use these distances since the path wouldn't be simple.
Any help would be appreciated.