시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 55 | 30 | 27 | 57.447% |
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 ≤ t ≤ 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 ≤ n ≤ 200 000): the number of vertices.
The next line contains n integers d1, d2, . . . , dn (1 ≤ di ≤ n − 1), the degree sequence of a tree.
It is guaranteed that Σdi = 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.
Camp > Petrozavodsk Programming Camp > Winter 2020 > Day 3: 300iq Petrozavodsk Contest III B번