My (author's) solution uses the fact that there are not many nodes having many children and nodes with not so many children are easy to handle.

Of course, as an author I don't want to reveal the full solution but I think this hint is enough for you to get it. I am happy to see many different approaches that didn't occur to me, including a good portion of HLD solutions.

I solved this using this technique e.e in $$$O(n \log^2 n)$$$, I can optimize it to $$$O(n \log n)$$$ using this blog.