For the first subtask, we note that to get the maximum height tree, we connect all of the tree parts into a straight line. Thus, the answer is equal to the single edge's cost plus the number of additional connections ~(N-2)~. For the minimum height tree, we will connect all of the unconnected tree parts to a single node that is part of the edge given. Thus, the answer is equal to the length of the edge.

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

For the second subtask, we note that the structure is already connected to form a tree, and thus, is static.

We first run an all-pairs shortest path algorithm, such as a BFS/DFS starting from each node, or Floyd-Warshall. Note that even though the graph is weighted, we can still use a BFS since the graph is a forest. For the maximum height, we simply find the longest path from one node to any other node in the tree. For the minimum height, we need to find the minimum longest path starting from each node.

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

For the third subtask, we use the same algorithm presented in subtask 2 to every single connected component in the forest. The difference is that now, we need to connect the trees together.

For the maximum case, we should connect the ends of all of the tree diameters together.

For the minimum case, we should connect all of the connected components to the component with the largest radius and thus, the answer is the largest radius. If there are two or more components with the largest radius, we must increase our answer by ~1~.

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

For the fourth subtask, we need an efficient method of finding the diameter of a tree. The diameter of a tree can be found by first running a BFS on any node and then another BFS starting from the last node of the previous BFS. The furthest distance found on the second BFS is the tree diameter.

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

For the fifth subtask, we need an efficient method of finding the radius of a tree. One way to accomplish this is to run DFS twice on each component. For both of the DFSes, we will start from a root node, which is chosen arbitrarily. Then, for the first DFS, find the length of the longest two paths starting from each node to the leaves of the tree. For the second DFS, each node will now consider if its longest path includes its parent. If the current node is not on the parent's longest path, then we check if the parent's longest path plus the edge in between is the largest or the second largest compared to the paths we have already computed for the current node. If the current node is on the parent's longest path, we use the parent's second longest path instead.

Alternatively, we can find the radius by simply finding the diameter of each tree, using the same method presented in the fourth subtask, and finding the most even split of each diameter.

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