I am trying to solve https://www.spoj.com/problems/QTREE4/ using centroid decomposition, but I am not able to solve it.

It would be appreciated if someone could help me with the approach.

Thanks in advance!