406776: GYM102538 B Best Tree

You are given the degree sequence of a tree (degrees of all its vertices, in arbitrary order).

Among all trees with the given degree sequence, find a tree with the largest maximum matching.

The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 100\,000 $$$): the number of testcases.

Next lines contain $$$t$$$ descriptions of a test case.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 200\,000$$$): the number of vertices.

The next line contains $$$n$$$ integers $$$d_1, d_2, \ldots, d_n$$$ ($$$1 \leq d_i \leq n-1$$$), the degree sequence of a tree.

It is guaranteed that $$$\sum{d_i} = 2(n-1)$$$ and that there is at least one tree with the given degree sequence.

Also, it is guaranteed that the total sum of $$$n$$$ in all test cases is at most $$$200\,000$$$.

For each test case, print one integer: the largest maximum matching among all trees with the given degree sequence.

2
10
1 1 2 2 2 2 2 2 2 2
5
4 1 1 1 1

5
1

In the first test case, you can construct a path with $$$10$$$ vertices, it will have the same degree sequence and the largest possible maximum matching.

In the second test case, the only possible tree is a star (one vertex connected with all others), and the largest matching for it is $$$1$$$.