Colored Subgraphs
Contest: Educational Codeforces Round 144 (Rated for Div. 2)
Difficulty rating: 2500
Tags: dfs and similar, dp, games, greedy, trees

Monocarp has a tree, consisting of $$$n$$$ vertices.

He is going to select some vertex $$$r$$$ and perform the following operations on each vertex $$$v$$$ from $$$1$$$ to $$$n$$$:

- set $$$d_v$$$ equal to the distance from $$$v$$$ to $$$r$$$ (the number of edges on the shortest path);
- color $$$v$$$ some color.

A nice coloring satisfies two conditions:

- for each pair of vertices of the same color $$$(v, u)$$$, there exists a path from $$$v$$$ to $$$u$$$ that only visits vertices of the same color;
- for each pair of vertices of the same color $$$(v, u)$$$, $$$d_v \neq d_u$$$.

Note that Monocarp can choose any amount of different colors he wants to use.

For each used color, he then counts the number of vertices of this color. The cost of the tree is the minimum of these numbers.

What can be the maximum cost of the tree?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$) — the description of an edge.

The given edges form a tree. The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase print a single integer — the maximum possible cost of the tree.

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

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

Example output:
4
1
3
3

Editorial:
Let's start by choosing a vertex $$$r$$$ naively. Iterate over all vertices and try each of them.
Root the tree by $$$r$$$ and observe what the conditions become. $$$d_v$$$ for each $$$v$$$ is just the depth of each vertex. Well, then the only case, when the connected subgraph of vertices of the same color has all values of $$$d$$$ distinct, is when they form a vertical path in the tree.
So the problem becomes the following. Split the tree into some vertical paths in such a way that the shortest path is as long as possible.
Let's try greedy, I guess. Start the paths from the leaves and propagate them up. Consider some vertex $$$v$$$ with at least two children. All children have some paths leading up to them. We'd love to continue them all with $$$v$$$, but we can't do that. We can only continue one path and cut the rest. Pretty easy to see that the path to continue is the shortest path available. It's at least as optimal as any other path.
Do that from the lowest vertices up, and you got yourself a working greedy. Also don't forget to stop all paths in root, since you can't continue any of them further up.
Let's make this greedy more formal. Every time we update the answer is with a path that is:
• the shortest in every vertex lower than the current one;
• not the shortest in the current one.
So we want to propagate the shortest child up and update the answer with the remaining children. Updating the answer means just taking the minimum of values. Thus, we can actually ignore all children except the second shortest in each vertex. Just don't forget to treat the root properly.
Now we can actually solve the problem in $$$O(n)$$$ for a fixed $$$r$$$. You can just find two minimums in each vertex.
Well, now that we can solve the problem for a single root, let's try rerooting to solve for all of them. There are solutions in $$$O(n)$$$ but I found the solution in $$$O(n \log n)$$$ the neatest. The constraints are low enough to allow it.
For each vertex, maintain a multiset of lengths of vertical paths from its children. I chose to store nothing in the leaves — that only makes the implementation cleaner. In order to update the vertex from its child, you can take the minimum element in the child's set and add $$$1$$$ to it. If it's empty (the child is a leaf), return $$$1$$$.
Additionally, store a multiset of the second minimums of all vertices that have at least two children.
In order to update the answer with the current root, find the minimum of that multiset and the shortest path from the root.
To achieve $$$O(n)$$$, you will probably have to either store prefix and suffix second minimums over children of each vertex or store three shortest paths in it. It is kind of messy but it should still perform better.
Overall complexity: $$$O(n \log n)$$$ or $$$O(n)$$$ per testcase.