For subtask 1, we simply try each possible pair of nodes for the meeting places and find the distance from each node to its closest meeting place with either DFS or BFS. This yields a time complexity of ~\mathcal{O}(N^3)~.

Time complexity: ~\mathcal{O}(N^3)~

For subtask 2, we notice that for any choice of meeting place, we can divide the tree into two connected components based on which meeting place the node is closer to. Thus to find the optimal solution, we can split the tree into two components by cutting an edge and then pick the centroid for each component to be the meeting place for each choice of the edge. Since we are given a chain for this subtask, we can use a two-pointer algorithm to find the centroids of each prefix and suffix of the chain. Afterwards, a prefix sum array can be used to find the total inconvenience for each component. The answer is thus the minimum possible sum of the two components after a split.

Time complexity: ~\mathcal{O}(N)~

For subtask 3, we use our idea from subtask 2, and split the tree from each edge. We can then find the centroid of both components as well as their inconvenience in ~\mathcal{O}(N)~. This gives an ~\mathcal{O}(N^2)~ solution.

Time complexity: ~\mathcal{O}(N^2)~

For subtask 4, we can adapt the idea that we used for subtask 3. First, we root the tree at node 1. Afterwards, for each subtree we will find its centroid as well as the centroid of its complement. However, since the centroid of a node's subtree and its complement does not differ too much from its parent node's subtree and its complement, we can find the centroid of the subtree by starting with the centroid of the parent node's subtree and continue walking along the heaviest branch until the centroid is found. The same can be done for the subtree's complement. It can be shown that if this is done for all the nodes then the total "movement" of the centroid of the two trees is ~\mathcal{O}(N)~.

Time complexity: ~\mathcal{O}(N \log N)~ or ~\mathcal{O}(N)~