Remove Exactly Two
Contest: Codeforces Round 1000 (Div. 2)
Difficulty rating: 1600
Tags: brute force, data structures, dfs and similar, dp, graphs, greedy, sortings, trees

Recently, Little John got a tree from his aunt to decorate his house. But as it seems, just one tree is not enough to decorate the entire house. Little John has an idea. Maybe he can remove a few vertices from the tree. That will turn it into more trees! Right?

You are given a tree$$$^{\text{∗}}$$$ of $$$n$$$ vertices. You must perform the following operation exactly twice.

- Select a vertex $$$v$$$;
- Remove all edges incident to $$$v$$$, and also the vertex $$$v$$$.

Please find the maximum number of connected components after performing the operation exactly twice.

Two vertices $$$x$$$ and $$$y$$$ are in the same connected component if and only if there exists a path from $$$x$$$ to $$$y$$$. For clarity, note that the graph with $$$0$$$ vertices has $$$0$$$ connected components by definition.$$$^{\text{†}}$$$

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$, denoting the two vertices connected by an edge ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$). It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the maximum number of connected components on a separate line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
On the first test case, removing a vertex twice will make the graph empty. By definition, the number of connected components in the graph with $$$0$$$ vertices is $$$0$$$. Therefore, the answer is $$$0$$$.

On the second test case, removing two vertices $$$1$$$ and $$$2$$$ leaves $$$2$$$ connected components. As it is impossible to make $$$3$$$ connected components with $$$2$$$ vertices, the answer is $$$2$$$.

On the third test case, removing two vertices $$$1$$$ and $$$5$$$ leaves $$$4$$$ connected components, which are $$$\left\{ 2,4\right\}$$$, $$$\left\{ 3\right\}$$$, $$$\left\{ 6\right\}$$$, and $$$\left\{ 7\right\}$$$. It can be shown that it is impossible to make $$$5$$$ connected components. Therefore, the answer is $$$4$$$.

Example input:
3
2
1 2
4
1 2
2 3
2 4
7
1 2
1 3
2 4
4 5
5 6
5 7

Example output:
0
2
4

Editorial:
The main observation behind this task is that the number of connected components increases by $$$\text{deg}-1$$$, where $$$\text{deg}$$$ is the degree of the removed vertex at the time of removing. Thus, the number of connected components after removing two vertices $$$i$$$ and $$$j$$$ is:
• $$$d_i+d_j-1$$$ if $$$i$$$ and $$$j$$$ are not adjacent;
• $$$d_i+d_j-2$$$ if $$$i$$$ and $$$j$$$ are adjacent, because removing $$$i$$$ will decrease $$$\text{deg}$$$ of $$$j$$$ by $$$1$$$.
The main approaches in maximizing this appear only after this observation. There are multiple approaches to this, where the editorial will introduce two of them.
• First Approach: Bruteforcing the First Vertex
You can maintain a sorted version of the degree sequence, using a std::multiset, a heap, or possibly even simply a sorted sequence.
After you fix the first vertex $$$i$$$, you can find the maximum degree after decreasing the degrees of all adjacent vertices by $$$1$$$. std::multiset can deal with this directly by removing and inserting values, while a heap or a sorted sequence can deal with this by popping elements from the end while the two maximums have the same value. Then, the second vertex is easily the one with maximum degree.
Maintaining the degrees takes $$$\mathcal{O}(d \log n)$$$ time. As $$$\sum d = 2m = 2(n-1) = \mathcal{O}(n)$$$, the total time complexity of this approach is $$$\mathcal{O}(n \log n)$$$.
• Second Approach: Bruteforcing the Second Vertex
If we greedily select the first vertex by degree, we can notice that selecting the first vertex as one with maximum initial degree will find at least one optimal solution. Assume that the first vertex with maximum degree had a maximum value $$$d_i+d_j-2$$$. Then, consider any solution with both vertices' initial degrees strictly less than $$$d_i$$$. This second solution's maximum possible value $$$d_{i'}+d_{j'}-1$$$ will never exceed $$$d_i+d_j-2$$$, because $$$d_{i'}<d_i$$$ and $$$d_{j'} \le d_j$$$. Thus, at least one optimal answer must have the first vertex as one with maximum initial degree.
But we do not know what to do when there are multiple first vertices with maximum initial degree. Luckily, trying only two first vertices with maximum initial degrees will always find one optimal answer. This can be proven by contradiction; If the two first vertices are $$$u$$$ and $$$v$$$, and the second vertex chosen in the bruteforce is $$$w$$$. At least one pair in $$$(u,v)$$$, $$$(u,w)$$$, $$$(v,w)$$$ will be not adjacent, because otherwise it implies the existence of a $$$3$$$-cycle, which can only exist if the graph is not a tree. Thus, if the optimal solution is in the form $$$d_u+d_w-1$$$, trying two first vertices will always find it.
Therefore, we can try two vertices greedily for the first vertex and try all other vertices as the second vertex, finding at least one optimal answer in the process.
The time complexity of this approach is $$$\mathcal{O}(n \log n)$$$ or $$$\mathcal{O}(n)$$$ depending on how adjacency is checked. Adjacency check in $$$\mathcal{O}(1)$$$ is possible by preprocessing parents using DFS, because "$$$u$$$ and $$$v$$$ are adjacent" is equivalent to "$$$par_u=v$$$ or $$$par_v=u$$$".