SPOJ QTREE4

general
, , , ,
1

Could someone help me understand and solve SPOJ QTREE4.

I’ve solved QTREE1-3 using HLD and Segment trees but the same approach doesn’t seem to work in this one.
Since, we need to find the longest shortest distance between any two white nodes in a tree usual segment tree methods aren’t working for me.

Can centroid decomposition be used in this question? If yes could someone please explain me how. I couldn’t find any good resources for the same apart from this link-

2

This link: https://www.quora.com/What-is-the-approach-to-solve-the-SPOJ-problem-QTREE4
describes a nice solution using Centroid Decomposition, although more tough to implement than SPOJ QTREE 1-3.