Help me in solving ADMN problem

My issue

I am not able to think of a approach for this question,only approach i was able to think was a greedy solution revolving around centroid.can someone please share their approach for this question?

Problem Link: ADMN Problem - CodeChef