For a vertex let B(c, r) be the set of vertices at distance at most from , and for an edge let B(uv, r) = B(u, r) \cup B(v, r). Both sets are connected (each vertex is joined to or by a path inside the set), and their diameters are at most and 2r+1 respectively.
Key observation. The answer for is the size of the largest ball of the matching parity:
(and for odd if n = 1).
By the bounds above, these balls are valid sets. Conversely, let be a connected set with diameter D \le x. Since is connected, distances inside equal distances in the tree. Take a path of length in and its middle: a vertex if is even, an edge if is odd. Every w \in S is within of the middle. Indeed, let be the vertex of the path closest to , say on the half towards ; then the route from to passes through and then through the middle, so if were farther than from the middle, we would get d(w, b) > D. Now fit into a ball of the right parity:
even, even: S \subseteq B(c, D/2) \subseteq B(c, x/2);
even, odd: S \subseteq B(uv, (D-1)/2) \subseteq B(u, (D+1)/2) \subseteq B(u, x/2);
odd, odd: S \subseteq B(uv, (D-1)/2) \subseteq B(uv, (x-1)/2);
odd, even: S \subseteq B(c, D/2) \subseteq B(cv, (x-1)/2) for any neighbour of (it exists unless n = 1).
Algorithm. Run a BFS from every vertex and count the vertices at each distance; the prefix sums of these counts are |B(c, r)| for all at once (for beyond the largest distance the ball is the whole tree). Keep the maximum for every . Do the same with a two-source BFS from both ends of every edge. This is 2n - 1 BFS runs of each, so the complexity is O(n^2) time and memory per test case.