The Maximum Subtree
Contest: Educational Codeforces Round 74 (Rated for Div. 2)
Difficulty rating: 2200
Tags: dfs and similar, dp, graphs, trees

Assume that you have $$$k$$$ one-dimensional segments $$$s_1, s_2, \dots s_k$$$ (each segment is denoted by two integers — its endpoints). Then you can build the following graph on these segments. The graph consists of $$$k$$$ vertexes, and there is an edge between the $$$i$$$-th and the $$$j$$$-th vertexes ($$$i \neq j$$$) if and only if the segments $$$s_i$$$ and $$$s_j$$$ intersect (there exists at least one point that belongs to both of them).

For example, if $$$s_1 = [1, 6], s_2 = [8, 20], s_3 = [4, 10], s_4 = [2, 13], s_5 = [17, 18]$$$, then the resulting graph is the following:

A tree of size $$$m$$$ is good if it is possible to choose $$$m$$$ one-dimensional segments so that the graph built on these segments coincides with this tree.

You are given a tree, you have to find its good subtree with maximum possible size. Recall that a subtree is a connected subgraph of a tree.

Note that you have to answer $$$q$$$ independent queries.

Input format:
The first line contains one integer $$$q$$$ ($$$1 \le q \le 15 \cdot 10^4$$$) — the number of the queries.

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

Each of the next $$$n - 1$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) denoting an edge between vertices $$$x$$$ and $$$y$$$. It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of all $$$n$$$ does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each query print one integer — the maximum size of a good subtree of the given tree.

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

Note:
In the first query there is a good subtree of size $$$8$$$. The vertices belonging to this subtree are $$${9, 4, 10, 2, 5, 1, 6, 3}$$$.

Example input:
1
10
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10

Example output:
8

Editorial:
At first let's understand which trees are good. For this, let's consider some vertex $$$v$$$ (we denote its segment as $$$[l_v, r_v]$$$) which is not a leaf. Also let's consider some adjacent vertex $$$u$$$ (we denote its segment as $$$[l_u, r_u]$$$) which also is not leaf. It is claimed that segment $$$[l_v, r_v]$$$ can't be inside segment $$$[l_u, r_u]$$$ (it's means $$$l_u \le l_v \le r_v \le r_u$$$) and vice versa. It's true because if segment $$$[l_v, r_v]$$$ is inside the segment $$$[l_u, r_u]$$$ then some vertex $$$t$$$ adjacent with $$$v$$$ also will be adjacent with $$$u$$$. So any non-leaf vertex can be adjacent with at most 2 non-leaf vertexes. Therefore good tree is a path with a leafs adjacent to this path.
So all the have to do it's find the such subtree of maximum size. We can do it by subtree dynamic programming.
At first, let chose the root of the tree — some not leaf vertex.
Let $$$dp_{v, 0}$$$ be the answer for the subtree with root in $$$v$$$ and dp_{v, 1} be the answer for the subtree with root in $$$v$$$ if we already took $$$v$$$ and its parent to the answer.
It can be calculated as follows:
• $$$dp_{v, 0} = \max\limits_{to} dp_{to, 0}$$$;
• $$$dp_{v, 0} = \max(dp_{v, 0}, deg_v + 1 + firstMax + secondMax)$$$, there $$$firstMax$$$ is a first maximum of all $$$dp_{to, 1}$$$, and $$$secondMax$$$ is a second maximum, and $$$deg_v$$$ is a degree of vertex $$$v$$$;
• $$$dp_{v, 1} = deg_v - 1 + \max\limits_{to} dp_{to, 1}$$$.