Subtask 1

For the first subtask, it suffices to find the diameter of each tree formed after removing a node. Recall that the diameter of the tree is the farthest distance between any two nodes. To find the diameter of a tree, we can run a depth first search from an arbitrary root and find the furthest node from that root. We can then run another depth first search from that node to find the furthest node. The diameter is equal to the distance to that node. We run this algorithm for each of the queries and find the largest of the diameters of each of the trees formed by removing that node. The answer is one greater than the length of the diameter.

Time Complexity: ~\mathcal{O}(N \cdot Q)~

Subtask 2

Recall the common dynamic programming solution to find the longest path in a tree. For each node, we will store the two longest paths that start at that node, and end in a node in its subtree (for some arbitrary root), such that the two paths do not share any edges in common. This can be done with a depth first search and storing the two longest paths of all adjacent nodes. The diameter is the maximum sum of the two longest paths for all nodes.

This dynamic programming method can be adapted for this subtask. For the second subtask, we can see that removing a node that is not in the diameter of the original tree will not result in the longest path of the remaining subtrees changing. When we do remove a node that is in the diameter of the tree, we need a way to find the longest path in all the resulting subtrees. We can run the dynamic programming algorithm twice on two different rooted trees, once with the root as one node of the original tree's diameter, and once with the other node of the diameter. Let these trees be called ~T_1~ and ~T_2~. Observe that for any node in the diameter of the tree, the union of the nodes in its subtrees in ~T_1~ and ~T_2~ is equal to the set of all nodes in the graph. Thus, for ~T_1~ and ~T_2~, we can store the longest path in its subtree with another depth first search, using the values computed from the dynamic programming algorithm. The maximum can then be stored for each node, and queries can be answered in constant time.

Time Complexity: ~\mathcal{O}(N + Q)~

Subtask 3

For the third subtask, we can build on the idea from the second subtask. When a node that is not in the diameter is removed, then one of the new trees that is formed has a diameter equal to the diameter of the original tree. We can see that each of the remaining trees are in the node's subtree for both ~T_1~ and ~T_2~. Thus, instead of only storing the maximum path length of all the trees as done in subtask 2, we can store the lengths of all the trees, for each node.

For nodes that are in the diameter of the tree, we can use a similar method, but will have to merge the answer arrays from the subtrees in ~T_1~ and ~T_2~. Be careful with handling duplicate vertices.

The answer can now be retrieved in constant time.

Time Complexity: ~\mathcal{O}(N \log N + Q)~