yukicoder 772 Dynamic Distance Sum

https://yukicoder.me/problems/no/772

The centroid gives the answer. So we should compute centroid quickly and calculate the sum of distances between the centroid and the marked vertices.

Looking at a edge, we obtain two trees by removing the edge. Either of them must has a centroid, and we can determine which one has the centroid. The tree with more marked vertices has the centroid. Repeating this property, we finally find the centroid [1].

But if we do it naively, it takes a lot of time. How should we do it? Top tree is known, but we can also use a like cut tree.
https://yukicoder.me/submissions/305340

[1] S. Alstrup, J. Holm, K. D. Lichtenberg, M. Thorup. Maintaining information in fully dynamic trees with top trees, Jornal ACM Transactions on Algorithms, 1(2), Pages 243--264, 2005.