Let's say your $k$ queries are in the following order $\{v_1, v_2, \ldots v_k\}$. For $v_1$, we will have no information so we simply do a DFS and determine the furthest node $u$ and return it. Consider $v_1$ to be the root of this DFS tree. For each of $v_1$'s children $\{u_1, u_2, \ldots\}$ we will also keep track of the deepest node in the subtree rooted at $u_i$. Let's call this $d(v_1, u_i)$. Note that the maximum distance node from $v_1$ is:
$$d(v_1) = \max_i d(v_1, u_i)$$
At this point, it is important to note that for the query $v_2$, we can retain a lot of information from $d(v_1, u_i)$ if the path to the furthest node from $v_2$ includes $v_1$. Let's assume w.l.o.g. that $v_2$ is in the subtree rooted at $u_j$ in the DFS tree of $v_1$. We will again do a DFS for the deepest node in the DFS tree of $v_2$, however when we hit $v_1$ we can stop and we only need to retain the distance $\delta(v_2, v_1)$. Now we compute $d(v_2)$ as:
$$d(v_2) = \max \{ \max_i d(v_2, y_i) , \ \delta(v_2, v_1) + \max_{i \neq j} d(v_1, u_i) \}$$
This idea can be repeated for the rest of the queries where $v_i$ relies on the information from the queries of $\{v_1, v_2, \ldots v_{i-1}\}$. At query $v_i$ we can describe the work as follows. Consider the DFS tree rooted at $v_i$, the "search" work done at any subtree rooted at $\{v_1, v_2, \ldots v_{i-1}\}$ is constant based on our precomputed values. We need only care about the work done before we reach these nodes. Here is an example analysis where we consider the query $v_{i+1}$ is in the "middle" of the largest remaining subtree.
- First query takes $cn$ and splits the tree into trees $T_1$ and $T_2$ of size $n/2$ each.
- Second query takes $cn/2$ and splits $T_1$ into trees $T_3$ and $T_4$ of size $n/4$ each.
- Third query takes $cn/2$ and splits $T_2$ into trees $T_5$ and $T_6$ of size $n/4$ each. At this point we have 4 trees: $\{T_3, T_4, T_5, T_6\}$.
- This goes on and on.
If we assume $k = 2^\ell - 1$, then we get the summation:
$$T(n) = \sum_{i = 0}^{\ell-1} 2^i\frac{n}{2^i} = O(\ell \cdot n) = O(n \log k)$$
As a side note, much of the work will depend on the ordering of the queries. For instance if we have a linked list of edges: $\{(v_1, v_2), (v_2, v_3), \ldots\}$ and we assume the query order is $\{v_1, v_2, \ldots v_k\}$ then:
- First query takes cn, and splits the tree into trees $T_1$ and $T_2$ of size $1$ and $n-1$ each.
- Second query takes c(n-1), and splits $T_2$ into trees $T_3$ and $T_4$ of size $1$ and $n-2$ each.
- Third query takes c(n-2), and splits $T_4$ into trees $T_5$ and $T_6$ of size $1$ and $n-3$ each.
- This goes on and on.
We get the final complexity is:
$$T(n) = \sum_{i = 0}^k c(n-i) = O(nk)$$
However, if we order the queries as $\{v_k, v_{k-1}, \ldots v_1\}$ then:
- First query takes cn, and splits the tree into trees $T_1$ and $T_2$ of size $k-1$ and $n-k + 1$ each.
- Second query takes c(k-1), and splits $T_1$ into trees $T_3$ and $T_4$ of size $k-2$ and $1$ each.
- Third query takes c(k-2), and splits $T_3$ into trees $T_5$ and $T_6$ of size $k-3$ and $1$ each.
- This goes on and on.
We get the final complexity is:
$$T(n) = cn + \sum_{i = 0}^{k-1} c(k-i) = O(n + k^2)$$
Even with an ordering of $\{v_k, v_{k/2}, v_{k/4}, v_{3k/4}, \ldots\}$ we could get a complexity of $O(n + k \log k)$. So the complexity very much depends on the ordering of the queries. If we assume the queries are random then this is still okay and we can get $O(n \log k)$. If we can re-order the queries then we can greedily pick the node that splits the tree closest to in-half and continue. This should give approximately $O(n \log k)$, though I have no proof and will not work through it here.