C. Remove Exactly Two time limit per test2 seconds memory limit per test256 megabytes
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∗ 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.†
∗ A tree is a connected graph without cycles.
† But is such a graph connected?
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104 ). The description of the test cases follows.
The first line of each test case contains a single integer n (2≤n≤2⋅105 ).
Each of the next n−1 lines contains two integers ui and vi , denoting the two vertices connected by an edge (1≤ui,vi≤n , ui≠vi ). 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⋅105 .
Output For each test case, output the maximum number of connected components on a separate line.
Example InputCopy 3 2 1 2 4 1 2 2 3 2 4 7 1 2 1 3 2 4 4 5 5 6 5 7 OutputCopy 0 2 4 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 {2,4} , {3} , {6} , and {7} . It can be shown that it is impossible to make 5 connected components. Therefore, the answer is 4 . Okay, let's see. The problem is about removing exactly two vertices from a tree and trying to maximize the number of connected components. Hmm. So each time we remove a vertex, we cut all its edges. The tree is initially connected, but after removing two vertices, the remaining parts might split into multiple components.
Let me think. When you remove a vertex v, all its adjacent edges are removed. So any neighbors of v that aren't removed become separate components. Wait, but if two neighbors are still connected through other paths, they might not be separate. Oh right, but since it's a tree, there are no cycles. So removing a node splits the tree into several parts equal to the number of its children, maybe? Or depends on the structure.
So the first idea is that removing two vertices can create multiple components. The maximum possible would depend on how their removal affects the tree's structure.
Let's consider some examples. The sample input for the third case has a tree structure where removing node 1 and 5 gives four components. Let's see why. Node 1 is connected to 2 and 3. Removing 1 would disconnect 2 and 3. Then node 5 is connected to 4,6,7. So removing 5 would split those into three parts. But wait, how do they connect in the original tree? The original tree is 1 connected to 2 and 3. 2 is connected to 4, which is connected to 5, which has 6 and 7. So when you remove 1 and 5:
The part under 2 (which is 4) is connected to 2? Wait, no. After removing 1, the edges from 1 to 2 and 3 are gone. So node 2 is still connected to 4. But when you remove 5, you cut edges between 5 and 4, 6,7. So 4's edge to 5 is gone. So node 4 is part of the component that includes 2 and 4 (since their connection is still there). Wait, but removing 5 would disconnect 4 from 5. So after removing 1 and 5, the remaining nodes are 2,3,4,6,7. Let's see:
Node 2 is connected to 4. So 2 and 4 form one component.
Node 3 is isolated, as its only connection was to 1 which is removed.
Node 6 is isolated (connected to 5 which is removed).
Node 7 is isolated (same as 6).
So that's 4 components. So the maximum here is 4.
The question is, how to find such a pair of nodes to remove to get the maximum possible components.
So the approach is to find two nodes whose removal creates as many disconnected parts as possible.
Each node's contribution when removed is equal to the number of edges it had. Because when you remove a node, each edge it had is cut, and each of its adjacent nodes (which are still present) becomes a separate component. But wait, no. Because if the adjacent nodes are not removed, but their other connections are also gone. For example, if a node has degree d, then removing it would split the tree into d parts. But this is only true if the node is a leaf. Wait, no. Wait, for a tree, when you remove a node of degree d, the number of components created is equal to the number of connected components that result. Since the original tree is connected, removing a node of degree d would split it into exactly d components, because each adjacent edge leads to a separate subtree. For example, if the node is a leaf (degree 1), removing it would split the tree into one component (the rest of the tree minus this leaf). Wait, no. Because the leaf is connected to one node. So removing the leaf (degree 1) just reduces the tree, but leaves it connected. So the number of components created by removing a leaf is zero. Wait, that's conflicting with previous thoughts.
Wait, perhaps I need to think again. Suppose we have a tree. If we remove a node v, which has degree d. Then the tree (which was connected) becomes d separate subtrees, each connected through their edges except for the edges that were connected to v. So yes, removing a node of degree d would split the tree into d components. For example, a star-shaped tree with a central node connected to many leaves. Removing the central node would split the tree into as many components as there are leaves.
But this is only true if the node is not a leaf. If the node is a leaf (degree 1), removing it just leaves the tree connected (since the rest of the tree is connected). So the number of components is 1, which is the original tree minus the leaf. Wait, but the original tree was connected, so after removing the leaf, it's still connected. So the number of components created by removing the leaf is 1 (the remaining tree) minus 1 (original was 1 component) is zero? Or the total components after removing is 1?
Wait, perhaps the initial tree has one component. After removing a node v, the components are the number of connected parts in the remaining graph. So, for example, removing a leaf (degree 1) would leave the remaining graph connected. So the number of components is 1. But the original component was 1, so the increase is zero.
But when you remove a node of higher degree, the number of components increases. For example, a node of degree 3. When removed, the three branches become separate components. So the new number of components is 3.
So, when you remove a node v of degree d, the number of components added is (d — 1). Because initially, the tree is 1 component. After removal, it's d components. So the increase is d-1.
But then, if two nodes are removed, how does their removal combine?
Suppose we remove two nodes, u and v. The total components would be the sum of (degree(u) + degree(v) — 2) minus any overlaps. Wait, maybe not. Because if removing u splits the tree into k components, then removing v (which is in one of those components) could split that component into m parts. So the total would be (k-1) + m.
Wait, perhaps the optimal case is to remove two nodes that are not adjacent. Then their contributions add up. But if they are adjacent, then removing the first node may split the tree into parts, and the second node is in one of those parts. So the second removal may split that part into several components, but the other parts remain as is.
Alternatively, perhaps the maximum number of components is (degree(u) — 1) + (degree(v) — 1) plus any possible additional splits if their removal regions are in separate parts.
Wait, this is getting complicated. Let's think of the maximum possible scenario. We need to select two nodes such that their removal causes the maximum possible components.
The maximum possible would be when the two nodes are each in positions where their removal splits the tree into as many components as possible, and these splits are independent.
For example, the first node has a high degree, and the second node is in one of the components split by the first node, but has high degree in that component.
Alternatively, the two nodes could be in different parts of the tree such that their removals split the tree into their respective degrees.
Wait, let's think of the third example again. The node 5 has degree 3 (connected to 4, 6, 7). Removing node 5 splits into 3 components. Then, if we remove node 1 (degree 2: connected to 2 and 3), that would split into two components. But since node 1 is in the same component as node 2 (since removing 5 splits into components including 4, which is connected to 2, which is connected to 1). So after removing 1, the component containing 2 and 4 would split into 2 (from node 1's removal) and 3. But wait, perhaps when you remove 1, you split the component into 2 parts. So overall, the total is 3 (from 5) + 2 (from 1) -1? Or maybe 3 + 1 (since the component where 1 is removed was part of the 3 components created by removing 5). So total would be 3-1 (since the component where 1 is was part of the 3) and then adding the new splits.
Alternatively, perhaps the maximum possible is the sum of the degrees of the two nodes minus 2. Because each node contributes (degree — 1) when removed. But if their removals are in different parts, perhaps the sum is (d1-1) + (d2-1). But in some cases, when the two nodes are adjacent, this sum might not be possible.
Wait, for example, if two nodes are adjacent. Let's say node u is connected to node v. If you remove u first, then removing v may not contribute as much. Or maybe they are part of a chain.
But maybe the maximum possible is the sum of (degree of u) + (degree of v) — 2. Because each contributes (degree -1) when removed. But we have to subtract 1 if the two nodes are adjacent. Because when you remove u, the edge between u and v is gone, so when you remove v, you lose one degree (since the edge to u is already removed). But wait, since when you remove u, you cut all edges from u, including u-v. So when you remove v, the edges to u are already gone, but v's other edges are still present. So the degree of v in the remaining tree (after removing u) would be (original degree of v — 1). So when you remove v, you split into (degree_v_remaining) components. So for example, if u and v are adjacent, and u is removed first, then when you remove v, you split into (degree_v_original — 1) components. So the total contribution for u and v would be (degree_u -1) + (degree_v -1 -1) if the order matters. Wait, but the order doesn't matter because the problem says you remove exactly two vertices, so perhaps the edges are cut for both. So the order of removal doesn't affect the final state.
Wait, when you remove two vertices, all edges incident to either of them are removed. So the edges connected to u are removed, and edges connected to v are removed, regardless of the order. So the final graph is the original tree minus all edges connected to u or v, and minus the nodes u and v.
So the effect is equivalent to removing all edges connected to u or v, and then removing u and v. So the way to compute the number of components is based on the remaining edges.
So the key is to find two nodes u and v such that the number of components after removing all edges connected to u and v is maximized.
Hmm. So each edge that is connected to u or v is removed. So the remaining edges are those that are not connected to u or v.
So the remaining graph is the original tree minus the edges connected to u or v. And then u and v are also removed. So any edges between nodes other than u and v, which are not connected to u or v, remain.
The connected components in this graph would be the parts of the original tree that are not connected through any path that doesn't go through u or v.
So, for example, if the tree is a path like a-b-c-d, and you remove a and d. Then the remaining nodes are b and c. The edges a-b and d-c are removed, but b-c is still there. So the remaining graph is b connected to c. So one component. So the total components would be 1.
But if you remove b and c, then the edges a-b, b-c, c-d are removed. The remaining nodes are a and d. So two components, each a single node. So two components. So this gives a higher count.
So the maximum depends on which two nodes you remove.
So how can we model this?
The approach is to model the graph after removing u and v, and all edges connected to them. The remaining edges are those that are not connected to u or v. The nodes remaining are all except u and v.
So, the connected components are determined by the original tree's structure, but with u and v and their edges removed.
So, the problem reduces to finding two nodes u and v such that when we remove them and all their edges, the number of connected components is maximized.
But how to compute that efficiently for a tree?
Let me think of the structure. The remaining graph is a forest, since we are removing edges from a tree. The forest's components are the parts that are not connected through edges involving u or v.
Each node in the remaining graph can be part of a connected component if they are connected via edges not involving u or v.
So, the connected components are the subtrees that are not connected to u or v. So for example, if the tree is rooted at u, then each child subtree of u would be a connected component if u is removed. But if we also remove v, which is in one of those child subtrees, then that subtree is split into parts not connected to v.
Wait, but in the remaining graph, any node that was connected via a path that doesn't go through u or v is part of the same component.
Alternatively, the remaining graph consists of all nodes except u and v, and edges not connected to u or v. So the connected components are the maximal sets of nodes where each pair is connected by a path that does not include u or v.
Hmm, but how to model this.
Another approach: the removal of u and v breaks the tree into parts. The number of connected components is equal to the number of separate subtrees that were connected to u and v. For example, if u has degree d1, and v has degree d2, but they are not adjacent. Then removing u splits the tree into d1 components, and removing v splits one of those components into d2 components, so total is d1 + d2 -1. But this is only if v is in one of the d1 components. So the total is (d1 -1) + (d2 -1) + ... ?
Wait, perhaps the maximum possible number of connected components is the sum of the degrees of u and v, minus 2, but only if u and v are not adjacent. Because if they are adjacent, then the edge between them is counted in both degrees. So when you remove both u and v, the edge u-v is removed twice (but in reality, it's only removed once). So the sum would be (d1 + d2 — 2) -1 (since the edge was counted twice). So the formula would be (d1 + d2 — 2) — 1 = d1 + d2 -3.
Wait, perhaps the maximum possible is (d1 + d2 — 2) if u and v are not adjacent, and (d1 + d2 — 3) if they are adjacent.
So, the maximum possible would be to choose two nodes u and v with the highest possible degrees, and check whether they are adjacent.
So the steps would be:
Find all pairs of nodes u and v, and compute the possible components as (degree[u] + degree[v] — 2) if they are not adjacent, or (degree[u] + degree[v] -3) if they are adjacent.
The maximum of these values would be the answer.
But wait, this might not always be the case. For example, there could be a scenario where even if two nodes are not adjacent, their removal creates more components than the sum of their degrees minus 2.
Hmm. Let's see.
Take the third example. The node 1 has degree 2 (connected to 2 and 3). Node 5 has degree 3 (connected to 4,6,7). Are they adjacent? No. So according to the formula, the sum is 2+3-2 = 3. But the sample answer is 4. So that formula is not correct. So there's a problem with this approach.
So this suggests that the formula is not correct and that another approach is needed.
Hmm. So maybe the initial approach was incorrect. So what's the correct way to model this?
Alternative approach: For each node, when you remove it, the number of connected components increases by (degree of node -1). Because removing a node of degree d splits the tree into d components (since it was connected before), so the increase is d-1.
But when you remove two nodes, the total increase is the sum of their individual contributions minus any overlaps.
But what's the overlap? For example, if the two nodes are in different components after the first removal, then the second node's removal would split their component again.
Alternatively, suppose after removing u, the tree is split into k components. Then, when removing v, if v is in one of those k components, the removal of v would split that component into m components, leading to a total of (k-1) + m components.
But how to compute this.
But since the two nodes are removed at the same time (order doesn't matter), perhaps the correct way is to model the effect of removing both.
Let me think of the tree as a collection of nodes connected by edges. When we remove u and v, all edges connected to u or v are removed. So the remaining edges are those not connected to u or v. The remaining graph is a forest, and the number of components is equal to the number of connected components in this forest.
So the problem reduces to: find two nodes u and v such that the number of connected components in the tree after removing all edges incident to u or v is maximized.
But how to compute this?
An alternative way to model this: each connected component in the remaining graph is a set of nodes that form a connected subtree in the original tree, and are not connected to either u or v.
Wait, no. Because even if they are connected through other nodes, as long as the path between them doesn't involve u or v.
Wait, but the remaining graph is the original tree with all edges adjacent to u or v removed, and u and v themselves removed. So the remaining edges are those that are not adjacent to u or v. So, any two nodes x and y in the remaining graph are connected if and only if there is a path in the original tree between x and y that does not pass through u or v.
But in a tree, the path between x and y is unique. So if that path passes through u or v, then x and y are not connected in the remaining graph. Otherwise, they are connected.
So the connected components in the remaining graph are the maximal subsets of nodes (excluding u and v) such that the path between any two nodes in the subset does not pass through u or v.
So, the number of connected components is equal to the number of subtrees that are "cut off" by removing u and v.
Another way to think: the remaining graph is the original tree minus the nodes u and v and all edges adjacent to them. The connected components are the subtrees that were connected to u or v, but are now disconnected from each other.
Wait, perhaps it's easier to model it as follows. Let's find all the edges that are removed (those adjacent to u or v). The remaining edges form a forest. The connected components are the number of trees in this forest, plus any isolated nodes (if any).
So, for each edge in the original tree, it's present in the remaining graph only if it is not adjacent to u or v. So the remaining edges are all edges except those connected to u or v.
But the nodes u and v are removed, so the remaining nodes are all except u and v.
So, the connected components in the remaining graph are the same as the number of connected components formed by the edges that are not adjacent to u or v.
But how to model this for all possible pairs u and v?
This seems computationally expensive if done naively, but perhaps there's a smarter way.
Alternative idea: For any pair of nodes u and v, the edges not connected to either form the edges of the remaining graph. The connected components are the parts of the original tree that are connected through paths that don't involve u or v.
So, each connected component in the remaining graph is a subtree that is connected through edges not adjacent to u or v. So, the number of components is equal to the number of "branches" that were connected to u or v and are now split off.
But how to model this.
Another approach: For each node, the removal of u will split the tree into several components. Then, removing v will split the component that v is in into more components.
But again, this is hard to model.
Alternatively, the maximum number of components after removing u and v is equal to the number of leaves in the tree when considering u and v as being removed.
Wait, perhaps not. Let's think of the third example again. Removing u=1 (degree 2) and v=5 (degree 3). The original tree has edges:
1-2, 1-3, 2-4, 4-5, 5-6, 5-7.
When we remove u=1 and v=5, the edges removed are all edges connected to 1 (1-2, 1-3) and all edges connected to 5 (4-5,5-6,5-7). The remaining edges are 2-4. The remaining nodes are 2,3,4,6,7.
So the remaining edges are 2-4. So the connected components are:
2 and 4 (connected via 2-4)
3 (no edges)
6 (no edges)
7 (no edges)
Total 4 components.
Which matches the sample. So the maximum is 4.
Now, how to find this.
Another approach is to realize that each node in the remaining graph (not u or v) must be part of a component. Each such component is a subtree that is connected through edges not involving u or v.
So, for example, the node 3 is connected to 1, which is removed. So node 3 becomes isolated. Similarly, nodes 6 and 7 are connected to 5, which is removed, so they are isolated. Nodes 2 and 4 are connected via an edge that's not removed (since 2 is connected to 4 via 2-4, which is not adjacent to u=1 or v=5. Wait, no. The edge 2-4 is present. Because u is 1, so edges connected to 1 are 1-2 and 1-3. The edge 2-4 is connected to 2 (not u or v), and 4 (which is not u or v). So the edge 2-4 is not removed. So nodes 2 and 4 form a connected component.
So in this case, the components are formed by:
- The subtree that is connected via edges not connected to u or v.
So the maximum number of components is determined by the number of "child" subtrees of u and v, but not overlapping.
Alternatively, for a node u, the number of components contributed by removing u is (degree of u). For v, it's (degree of v). But if the two are connected, then one of the components is overlapping, so we subtract 1.
Wait, but in the third example, u=1 (degree 2) and v=5 (degree 3), which are not connected. So their degrees sum to 2 + 3 = 5. But the answer is 4. So that approach is also not working.
Hmm. So perhaps the correct formula is (degree[u] + degree[v] — overlap), where overlap is 1 if u and v are adjacent, 0 otherwise.
In the third example, 2 +3 =5, and since they are not adjacent, overlap is 0. So 5-0=5. But sample answer is 4. So that's not matching.
Alternatively, maybe the formula is (degree[u] — 1) + (degree[v] -1) — (if they are adjacent, 1 else 0).
In the third example, (2-1)+(3-1) = 1+2=3. But sample answer is 4. So no.
Hmm. So this approach is not working.
Alternative Idea: Let's model the number of components as the sum of the degrees of u and v minus the number of shared edges between them.
Wait, but u and v can have at most one edge between them (since it's a tree).
So if u and v are connected, then their edge is removed once. So the total edges removed is (degree[u] + degree[v] — 1), since the edge u-v is counted in both degrees but is only removed once.
But how does that relate to the number of components.
In the original tree, each edge removed can split the tree into more components. But perhaps the number of components after removing u and v is equal to the number of edges removed that are in the tree's edges. Wait, not sure.
Alternatively, the number of components is equal to the number of edges removed that are part of the tree's bridges. Because in a tree, every edge is a bridge. So when you remove edges, each removed bridge increases the number of components by 1.
But in this case, when you remove edges adjacent to u and v, you are removing certain bridges. The number of components is the number of edges removed (since each edge removal splits the tree into two parts). But this is not exactly correct because removing multiple edges can split the tree into multiple components.
Wait, for example, removing three edges from a star-shaped tree (central node with three edges). Removing all three edges would split the tree into three components. But the number of edges removed is three, and the number of components is three.
But the number of components is equal to the number of edges removed if all edges are connected to the same node. Because each edge removal creates a new component.
So perhaps the number of components after removing u and v is equal to the number of edges removed that were in the original tree, but only considering edges connected to u or v.
Wait, but this can't be right. For example, in the third example:
Edges removed are 1-2, 1-3, 4-5,5-6,5-7. So total 5 edges removed. The original tree has 6 edges. The number of components after removal is 4, which is not equal to 5.
So that approach is incorrect.
Alternative Idea: The number of components after removing u and v is equal to the number of connected components in the remaining graph. The remaining graph has all nodes except u and v, and edges that are not connected to u or v. So for each node w not equal to u or v, the edges of w that remain are those edges that are not connected to u or v.
So, the connected components are the maximal subsets of nodes (excluding u and v) where there exists a path between any two nodes in the subset that does not pass through u or v.
In a tree, the path between two nodes is unique. So, two nodes x and y (not u or v) are in the same component if their unique path in the original tree does not pass through u or v.
So, for x and y to be in the same component, their path must not include u or v as internal nodes. But u and v are removed, so even if the path would have passed through u or v, but since those nodes are removed, the path is broken.
Wait, but in the original tree, the path between x and y is unique and may pass through u or v. If the path passes through u or v, then in the remaining graph, x and y are not connected (since u and v are removed, along with all their edges). So x and y can only be connected in the remaining graph if their path in the original tree does not go through u or v.
So the number of components is equal to the number of pairs of nodes (x, y) in the remaining graph where their original path doesn't pass through u or v. But this is not helpful.
Alternative Idea: For each pair of nodes u and v, the number of components after removing them is equal to the number of subtrees that are "attached" to u or v. For example, each child subtree of u (excluding the path to v) contributes one component, and each child subtree of v (excluding the path to u) contributes another component.
Wait, perhaps this is the way to model it.
Let me think. For a given u and v:
- Consider the tree as rooted at u. The children of u are its neighbors. For each neighbor of u, except the one leading to v, their subtree becomes a separate component.
Similarly, for v, the neighbors except the one leading to u, their subtrees become separate components.
But if u and v are not adjacent, then the path between them is through some other nodes. So, in that case, removing u and v would split the tree into several components based on their respective neighbors and the path between them.
This seems complicated.
Alternative Idea: For any node u, the number of components created by removing u and another node v is equal to the sum of the number of children of u (not in the path to v) and the number of children of v (not in the path to u) plus any other splits caused by the removal of the path between u and v.
But how to model this.
Alternatively, think of the tree as a collection of paths. When you remove u and v, any subtree connected to u (except those along the path to v) and any subtree connected to v (except those along the path to u) form separate components. Additionally, the path between u and v is split into a chain that may form a component if some nodes are not removed.
But this is getting too vague.
Perhaps an efficient way is to precompute for each node the number of children, or the degrees, and then find the pair u and v that maximizes (number of children of u not in v's subtree) + (number of children of v not in u's subtree) + 1 if the path between u and v is non-empty.
Alternatively, the maximum number of components is the sum of the degrees of u and v minus the number of edges on the path between u and v. But I'm not sure.
Let's try this for the third example. u=1, v=5. Path between them is 1-2-4-5. So the number of edges on the path is 3. The degrees of u is 2, v is 3. So sum is 2+3=5. Subtract the edges on the path (3) gives 2. But sample answer is 4, so this is not correct.
Alternatively, perhaps the formula is (degree[u] + degree[v] — (number of common edges in the path from u to v)).
But this is unclear.
Alternative Idea: Let's think of the nodes u and v. For each, the number of edges removed is degree[u] + degree[v] — overlap, where overlap is 1 if u and v are connected (since their mutual edge is counted in both degrees but removed once).
But how does this affect the number of components.
Each edge removed from the tree can potentially split the tree into more components. But in a tree, each edge is a bridge, so removing an edge increases the number of components by 1.
So the number of components after removing edges connected to u and v is equal to the number of edges removed that are bridges (which is all of them), but since the tree is connected, the number of components created is (number of edges removed) + 1 — n_original_components. But the original tree has 1 component, so the number of components after removal is (number of edges removed) + 1 — 1 = number of edges removed. Wait, no. Because each edge removed increases the component count by 1. For example, a tree with 2 nodes and 1 edge. Removing the edge increases components from 1 to 2. So number of edges removed (1) = components after removal (2-1=1). So the formula is components = edges_removed + 1.
But this is not correct. For example, a tree with 3 nodes in a chain A-B-C. Removing the B-C edge increases components to 2. Edges removed is 1. 1+1=2. Correct. Now, remove edges A-B and B-C (both edges). Components are 3. Edges removed is 2. 2+1=3. Correct.
So the formula components after removing certain edges is (number of edges removed) + 1. But this is only if the edges removed are all bridges, which in a tree they are.
But in our case, the edges removed are all edges adjacent to u or v. So the number of edges removed is (degree[u] + degree[v] — overlap), where overlap is 1 if u and v are adjacent.
So the number of components after removing u and v's edges is (degree[u] + degree[v] — overlap) + 1.
But then we also remove the nodes u and v. How does that affect the components?
When you remove the nodes u and v, you split any components that include them into smaller components. For example, if after removing the edges, the tree is split into components that include u or v, removing those nodes will split each component containing them into possibly more components.
But this is getting complicated.
Alternative Idea: When we remove u and v and all edges connected to them, the remaining nodes are all except u and v, and the remaining edges are those not connected to u or v. The number of components in this remaining graph is what we need to find.
But how to compute this.
Let's think of it this way: Each edge not connected to u or v remains. So the connected components are the maximal sets of nodes (excluding u and v) where each pair is connected by a path that doesn't pass through u or v.
But in a tree, the path between any two nodes is unique. So if that path passes through u or v, then they are not connected in the remaining graph.
So for each node x (not u or v), its component is the set of all nodes y (not u or v) such that the path from x to y in the original tree does not pass through u or v.
So, the number of components is equal to the number of such regions that are disconnected from each other after removing u and v.
But how to model this.
Another approach: For a given u and v, the components are formed by the subtrees that are attached to the path between u and v but are not part of that path.
For example, consider the path between u and v. Along this path, there are various nodes. Each node along the path can have branches (subtrees) that are not part of the path. Each of these branches becomes a separate component when u and v are removed. Additionally, the parts of the path between u and v that are not connected to any other branches would form a single component if they are not removed, but since u and v are removed, the path between them is split into a chain of nodes that are not connected to anything else.
Wait, this is getting complicated. Let's take the third example again.
u is 1, v is 5. The path between them is 1-2-4-5. The nodes along the path are 1,2,4,5. But u and v are removed. So the nodes along the path are 2 and 4.
The branches attached to the path are:
From node 1: there are branches 3 (but u is removed, so this branch is now a single node).
From node 2: in the original tree, node 2 is part of the path. But after removing u and v, node 2's other edges (like 2-4) are still present. So node 2 is connected to 4.
From node 4: in the path to 5. But 5 is removed, so the branch from 4 to 5 is removed. But node 4 is still connected to 2.
From node 5: branches 6 and 7. These are removed when 5 is removed.
So the remaining nodes are 2,3,4,6,7.
The edges are 2-4. So components are:
2 and 4 (connected via 2-4)
3 (isolated)
6 (isolated)
7 (isolated)
Total 4 components.
So the components are formed by the subtrees attached to the path between u and v, which are not part of the path.
Each node that was in a subtree attached to the path (but not part of the path) becomes a component when u and v are removed. Also, the nodes along the path between u and v that are not u or v (like 2 and 4) form a component if they are connected via edges not removed.
In this case, nodes 2 and 4 are connected via 2-4, which is not removed. So they form a component.
So the number of components is:
- For each node on the path between u and v (excluding u and v), the number of branches (subtrees) attached to them that are not part of the path.
Plus the number of branches attached to u and v that are not on the path.
Wait, this is getting too complex. Perhaps the correct way is to think of all the nodes not on the path between u and v. Each of these nodes belongs to a subtree that is connected to the path through either u or v. Removing u and v disconnects these subtrees, so each such subtree becomes a separate component.
Additionally, the path between u and v (excluding u and v) may form a component if they are connected via edges not removed. But if the path is broken due to removal of edges from u and v, then each part becomes separate.
But how to model this.
Alternative Idea: The number of components after removing u and v is equal to the number of leaves in the original tree that are not in the path between u and v, plus the number of connected components in the path between u and v after removing u and v.
But this is not correct.
Alternatively, think of the tree as divided into three parts:
The subtree(s) connected to u but not through v.
The subtree(s) connected to v but not through u.
The path between u and v.
When you remove u and v, part 1 and 2 become separate components. The path between u and v, if any, may form a chain. But since u and v are removed, this chain is split into a set of nodes that are connected if they are not removed. For example, if the path is u — a — b — v, then removing u and v leaves a and b. If there are edges between a and b (which are not removed), then they form a component. Otherwise, they are separate.
But in a tree, the path between u and v is a chain of nodes. Each node in this chain (except u and v) may have their own subtrees that are not part of the chain. These subtrees are part of the components formed when u and v are removed.
So the total number of components is:
For each node in the path between u and v (excluding u and v), the number of subtrees attached to them that are not part of the path. Each of these subtrees becomes a component.
The number of subtrees attached to u that are not on the path to v. Each becomes a component.
The number of subtrees attached to v that are not on the path to u. Each becomes a component.
The nodes along the path between u and v (excluding u and v) form a single component if they are connected through edges not removed. For example, if the path is u — a — b — v, then the edges a-b are part of the path and not removed (since they are not adjacent to u or v). So a and b form a component.
So the total components would be:
subtree_components + path_components.
Where subtree_components is the sum of:
(degree[u] — 1) [number of subtrees of u not on the path to v]
(degree[v] — 1) [number of subtrees of v not on the path to u]
For each node on the path between u and v (excluding u and v), the number of subtrees attached to them not on the path.
Plus path_components, which is 1 if the path between u and v (excluding u and v) has at least one node and is connected (which it is, since the path is a chain and edges between them are not removed).
So for example, in the third example:
u is 1, v is 5.
Path between u and v is 1-2-4-5.
Nodes on the path (excluding u and v) are 2 and 4.
Subtree_components:
u (1) has degree 2. The path to v is through 2. So subtrees not on the path: 3. So 1 component.
v (5) has degree 3. Path to u is through 4. So subtrees not on the path are 6 and 7. So 2 components.
Node 2 on the path: its subtrees not on the path are none (it has one edge to 4, which is part of the path, and one edge to 1 which is removed). So 0.
Node 4 on the path: its subtrees not on the path are none (it's connected to 2 and 5, which are part of the path). So 0.
So subtree_components is 1 + 2 = 3.
Path_components: 2 and 4 are connected via 2-4, which is not removed. So they form 1 component.
Total components: 3 + 1 = 4.
Which matches the sample.
Another example: the second test case.
Sample input:
4
Edges: 1-2, 2-3, 2-4.
If we remove nodes 1 and 2.
The path between them is 1-2.
Subtree_components:
u=1 has no subtrees not on the path (since it's a leaf).
v=2 has two subtrees not on the path: 3 and 4. So 2 components.
Nodes on the path (none, since u and v are directly connected).
Path_components: since u and v are removed, the path between them is empty. So path_components is 0.
Total components: 2.
Which matches the sample.
So this approach seems to work.
So the formula for the number of components after removing u and v is:
(degree[u] — 1) + (degree[v] — 1) + sum over nodes on the path between u and v (excluding u and v) of (degree[node] — 2) ) + 1 (if the path between u and v has length >= 2).
Wait, because for each node on the path between u and v, the degree in the original tree is 2 (since they are on the path, and in a tree, each node on the path between u and v has exactly two neighbors: one towards u and one towards v. Unless the node is a branch point. Wait, no. For example, node 2 in the third example is part of the path between 1 and 5, and has degree 2 (connected to 1 and 4). But in the tree, node 2 has degree 2. So when we compute degree[node] — 2 for nodes on the path between u and v, for such nodes, it's 0. So those nodes contribute nothing. So in the third example, the sum is 0 for nodes 2 and 4.
But in a case where a node on the path has a higher degree, like node A is on the path between u and v, but also connected to other nodes, then degree[A] — 2 would be the number of subtrees attached to A that are not on the path.
So the formula would be:
components = (degree[u] — 1) + (degree[v] — 1) + sum (degree[ p ] — 2 for p in path between u and v excluding u and v) + (1 if path_length > 1 else 0).
Because when the path between u and v has more than one edge (i.e., path_length >= 2), the nodes between them form a connected component.
But path_length is the number of edges between u and v. For example, if u and v are adjacent, path_length is 1. So the path between them has length 1, so the nodes on the path are u and v. So the path between them has no other nodes, so sum is zero, and path_length >1 is false. So the path_components is 0.
So let's see:
For the second example:
u=1 and v=2. path_length is 1. So:
components = (degree[1]-1) + (degree[2]-1) + sum(degree[p]-2 for p in path) + 0.
degree[1] is 1, so (1-1)=0.
degree[2] is 3, so (3-1)=2.
sum is 0 (since path has no nodes between u and v).
So components= 0+2 +0 +0= 2. Which matches the sample.
Another example: first test case. Removing nodes 1 and 2. Both are leaves. path_length is 1. sum is zero.
components = (1-1)+(1-1) +0 +0=0. Which matches the sample.
So the formula works.
Now, the problem reduces to finding two nodes u and v that maximize this formula.
The question is, how to compute this efficiently for all possible pairs u and v in a tree.
But considering that t is up to 1e4 and n up to 2e5, we need an O(n) or O(n^2) approach. But O(n^2) is impossible for n=2e5. So we need a way to find u and v that maximize this formula.
But how?
The formula is:
components = (d_u -1) + (d_v -1) + sum (d_p -2 for p in path between u and v excluding u and v) + (1 if path_length >=2 else 0).
This can be rewritten as:
components = (d_u + d_v — 2) + sum (d_p -2 for p in path between u and v excluding u and v) + (1 if path_length >=2 else 0).
So, the components depend on the degrees of u, v, the degrees of the nodes along the path between them, and the path length.
To maximize this, we need to choose u and v such that:
d_u and d_v are as large as possible.
The sum of (d_p -2) for nodes along the path between u and v is as large as possible.
Additionally, if the path between u and v has at least two edges, we get an extra 1.
So, the optimal pair u and v would likely have high degrees, and the path between them passes through nodes with high degrees.
But how to find such pairs efficiently.
Alternatively, perhaps the maximum is achieved when u and v are two leaves (degree 1), but this would give components (1-1) + (1-1) + ... =0. Not optimal.
So the optimal pair must be two nodes with high degrees.
But the third example has u with degree 2 and v with degree 3, which are not the highest degrees possible. But it gives a higher sum than if choosing higher degrees.
So the formula is not straightforward.
Alternatively, perhaps the maximum components is achieved by choosing two nodes u and v that are not connected by a path, but that's impossible in a tree.
Alternatively, the best way is to find two nodes u and v such that their path contains as many nodes with degree >=3 as possible. Because each such node contributes (d_p -2) to the sum.
But this is still unclear.
Alternatively, for each node, we can compute a value that is (degree of u) plus the sum of (degree of p -2) for all nodes in its subtree. Then, find two nodes u and v where their combined values plus path-related terms are maximized.
But I'm not sure.
Perhaps the easiest way is to precompute for each pair of nodes the sum of (d_p-2) along their path, and then compute components as (d_u + d_v -2) + sum + (1 if path length >=2).
But how to compute this sum for all pairs efficiently.
The sum over the path between u and v of (d_p-2) is equal to the sum of (d_p) along the path minus 2*(path_length).
So sum (d_p-2) for p in path excluding u and v) = sum (d_p) for p in path (excl. u and v) — 2*(path_length).
But path_length is the number of edges between u and v, which is equal to the number of nodes in the path minus 1.
So if the path has k nodes (including u and v), the number of edges is k-1. So the number of nodes in the path excluding u and v is (k-2). So sum (d_p-2) for p in path (excl. u and v) is sum(d_p) for those nodes minus 2*(k-2).
But this seems complicated.
Alternatively, the sum (d_p — 2) for all nodes on the path between u and v (excluding u and v) is equal to (sum of degrees of those nodes) — 2*(number of such nodes).
But how to compute this for any pair u and v.
This seems like a problem that can be handled using Lowest Common Ancestor (LCA) techniques. Because the path between u and v is the path from u to LCA(u, v) to v. So for each pair of nodes, we can compute the sum of degrees along their path.
But even with that, for large trees, computing this for all pairs is O(n^2), which is not feasible.
So there must be a smarter way.
Alternative Idea: The maximum possible components is achieved by selecting two nodes u and v such that their removal leaves as many leaves as possible. Because each leaf in the remaining graph is a component.
But I'm not sure.
Alternatively, think of the optimal pair as being two nodes that are leaves of the tree. But that would give (1-1)+(1-1) + ... =0, which is not good.
So that's not helpful.
Another Idea: The sum of (d_p -2) along the path between u and v is maximized when the path passes through as many nodes with high degrees as possible. For example, a node with degree 4 would contribute 2 to the sum (4-2=2). So the path should include as many high-degree nodes as possible.
So the optimal u and v would be two nodes whose path passes through the maximum number of high-degree nodes.
But again, how to find such a pair.
Alternatively, the best way to maximize the sum is to choose two nodes u and v where their path is through a node with maximum possible (d_p -2). For example, if there's a node p with degree 5, then (d_p-2)=3. Choosing u and v such that their path goes through p would add 3 to the sum.
But this is just speculation.
Perhaps the best way is to iterate through all pairs of nodes, but that's not feasible for large n.
So, given the time constraints, perhaps there's a way to approximate the maximum possible by considering certain candidates.
For example:
The two nodes with the highest degrees.
The node with the highest degree and its neighbor with the next highest.
Nodes that are leaves (degree 1) and the node with highest degree.
But this might not capture all possibilities.
Alternatively, the maximum possible components can be found by considering the sum (d_u + d_v) and selecting the pair with the highest sum. This is based on the assumption that the sum of their degrees is the main contributor to the formula.
But in the third example, d_u=2 and d_v=3, sum 5. Another pair might have higher sum. For example, nodes 2 (degree 3) and 5 (degree 3). Their sum is 6. Let's compute the components for this pair.
Nodes 2 and 5. Path between them is 2-4-5. So path_length is 2.
Components:
d_u=3 (node 2) has degree 3. The path to v is through 4. So subtrees not on the path are 1 and 3. But node 1 is connected to 2. When node 2 is removed, those subtrees (1 and 3) are isolated. So (3-1)=2 components from u.
d_v=3 (node 5) has degree 3. The path to u is through 4. So subtrees not on the path are 6 and 7. So (3-1)=2 components from v.
Sum (d_u-1) + (d_v-1) = 2+2=4.
Sum along path (nodes 4):
d_p=2 (node4). d_p-2=0. Sum is 0.
Path_length=2, so add 1.
Total components=4+0+1=5.
But in the third example, the sample answer is 4. So if this pair gives 5 components, then the sample answer is wrong, which is not possible. So this suggests that my formula is incorrect.
Wait, let's reevaluate. If u is node 2 and v is node 5, then:
- Removing u and v and all edges connected to them.
Edges connected to u (2): 1-2, 2-4, 2-3.
Edges connected to v (5):4-5,5-6,5-7.
So the remaining edges are 1-3 (no), 4-5 (no), etc. Wait, no. The remaining edges are those not connected to u or v.
So the remaining edges are:
1-2 is connected to u, removed.
2-3 is connected to u, removed.
2-4 is connected to u, removed.
4-5 is connected to v, removed.
5-6 is connected to v, removed.
5-7 is connected to v, removed.
1-3: not present.
Wait, the original tree has edges:
1-2, 1-3, 2-4,4-5,5-6,5-7.
So after removing u=2 and v=5, the remaining edges are:
1-3 (connected to 1, which is not removed, and 3, not removed).
So the remaining nodes are 1,3,4,6,7.
The edges remaining are 1-3.
So the components are:
- 1 and 3 (connected via 1-3)
-4 (isolated)
-6 (isolated)
-7 (isolated)
Total 4 components.
But according to the formula, it should be 5. So the formula is not correct. This indicates a flaw in the previous reasoning.
So the formula must be wrong. So the approach to model this problem as the sum of (d_u-1)+(d_v-1) plus some other terms is not correct.
So we need to find another way.
Perhaps the correct approach is to realize that the number of components is equal to the number of nodes that were leaves in the original tree and are now isolated, plus the number of connected components formed by non-leaf nodes.
But again, this is not clear.
Alternative Idea: For any pair of nodes u and v, the number of components after removing them is equal to the number of leaves in the original tree that are not in the path between u and v.
But this is not correct.
Another Idea: Let's think of each node that is a neighbor of u or v. Each such neighbor, if not removed, becomes a component if all its edges except those to u or v are removed.
But this is not necessarily true.
Perhaps the correct way to compute the number of components is:
For each node x not u or v:
- If x is connected to u or v, then x is part of a component that includes all nodes in the subtree rooted at x (excluding u and v).
But again, this is not clear.
Alternative Idea: The number of components after removing u and v is equal to the number of connected components in the original tree that are not connected to u or v.
But this is not correct.
Alternative Idea: For each node x, the component x is in is the set of nodes y such that the path from x to y in the original tree does not pass through u or v.
So the number of components is the number of such connected regions.
So, the problem reduces to finding the maximum number of such regions over all pairs of nodes u and v.
But how to compute this.
Another approach: The maximum number of components is achieved by choosing two nodes such that their removal creates as many "separate" subtrees as possible. For example, each subtree connected to u and each subtree connected to v should be separate.
The maximum possible is when u and v are connected through a single node, and both have many branches.
But I'm not sure.
Another Idea: The maximum number of components is the sum of the two largest degrees minus 2. For example, in the third test case, the two largest degrees are 3 (node 5) and 3 (node 2). Sum is 6-2=4. Which matches the sample.
In the second test case, the largest degrees are node 2 (3) and node 1 or 3 or 4 (1). Sum 3+1-2=2, which matches.
In the first test case, two nodes with degree 1. Sum 1+1-2=0.
So this seems to work.
But what about the case where the two nodes are adjacent.
For example, a star-shaped tree with central node c connected to a, b, d, e. So degree of c is 4. Nodes a, b, d, e have degree 1.
If we remove c and a.
Then, removing c (degree 4) and a (degree 1). The components would be:
- b, d, e are connected to c, but c is removed. So each is isolated. So 3 components.
So the sum of degrees 4+1-2=3, which matches.
If we remove c and another node, say d. Then the components are a, b, e. So 3 components. So sum 4+1-2=3.
If we remove c and another node with degree 1, the sum is 4+1-2=3.
But if we remove two nodes of degree 1, say a and b. Their sum is 1+1-2=0. Which is correct, as removing them leaves c, d, e connected to c. So components is 1.
So this formula seems to work.
But why? Because when you remove u and v, each of their edges (except possibly the edge between them) are removed. The sum of their degrees minus 2 gives the number of edges removed (if they are not adjacent). But each edge removed increases the component count by 1. So the number of components after removing u and v is (sum of degrees of u and v) — 2 + 1 (original component).
Wait, no. Because the initial component is 1. Each edge removed increases the component count by 1. So the number of components after removing edges is (number of edges removed) + 1.
But the number of edges removed is (d_u + d_v — overlap), where overlap is 1 if u and v are adjacent.
So components is (d_u + d_v — overlap) + 1 — 1 (since nodes u and v are also removed, which can split components into smaller ones).
Wait, this is getting too convoluted.
But according to the examples, the formula sum of degrees of u and v minus 2 (if they are not adjacent) gives the correct answer.
But in the previous example where u and v are adjacent, like removing c and a (adjacent), the formula gives 4+1-3=2 (since overlap is 1, so sum is d_u +d_v — overlap -2 +1? Or maybe not.
Wait, in the star example, removing c and a:
d_u =4 (c), d_v=1 (a). They are adjacent.
The formula sum (d_u +d_v -2) — 1 (overlap) = (4+1-2)-1=2. But the actual components are 3.
So this formula is not correct.
Hmm. So this suggests that the previous approach of summing degrees and subtracting 2 is incorrect.
But in the third example, the two nodes are not adjacent, and the sum of degrees is 2+3=5. Subtract 2 gives 3. But the sample answer is 4.
So this approach also fails.
So this suggests that there's a different way to model the problem.
After spending a lot of time trying to find a pattern, perhaps the correct way is to realize that the maximum number of components after removing two nodes u and v is the sum of their degrees minus 2 if they are not adjacent, and sum of their degrees minus 3 if they are adjacent. This would give the correct result for the third example (2+3-2=3), but the sample answer is 4, which contradicts this.
Thus, this approach is not correct.
Alternative Idea: Perhaps the maximum number of components is determined by the number of leaves in the tree. For example, if you remove two leaves, you get zero components. If you remove two nodes with high degrees, you get more components.
But how.
Another Idea: The number of components after removing u and v is equal to the sum of the degrees of u and v minus 2 (if they are not adjacent), or minus 3 (if they are adjacent). But this doesn't hold in the third example.
But the third example's answer is 4, which is 2+3-1 =4. But I'm not sure where that comes from.
Alternative Idea: Let's think of the problem as follows. Removing u and v:
Each neighbor of u that is not v becomes a component.
Each neighbor of v that is not u becomes a component.
If u and v are adjacent, then their mutual neighbor is counted in both, so subtract 1.
So the number of components is (degree[u] — 1) + (degree[v] — 1) — (if u and v are adjacent, 1 else 0).
But this formula:
In the third example, (2-1)+(3-1) =1+2=3. Since u and v are not adjacent, subtract 0. So 3. But the sample answer is 4. So this is incorrect.
But wait, the third example's components are 4. So this formula is missing something.
Ah, right. Because when you remove u and v, their neighbors are not the only components. For example, node 4 is connected to 2, which is not removed. So 2 and 4 form a component. So the formula is missing components formed by nodes not directly connected to u or v.
So this approach is incorrect.
Another Idea: The correct answer is the sum of the degrees of the two nodes, minus 2 if they are adjacent, plus the number of nodes in the path between them that have degree 2.
But this is just a guess.
After spending a lot of time on this, I think the correct approach is to realize that the maximum number of components is the sum of the two highest degrees in the tree minus 2 if they are not adjace
