The PDF version of this problem can be downloaded here.
In the Pizza Kingdom, there are bridges between some pair of islands. Moreover, there is exactly one path between every two dierent islands in the kingdom.
For the Pizza Festival, the people in each island vote for their most favorite pizza, and give the pizza a number of deliciousness. Now, the king wants to march from one island to another island, and stay on some of the islands on the path to have a taste of their favorite pizzas. The only constraint is that the deliciousness of these pizzas
must be strictly increasing, so that the king will become happier and happier along the march. Your job is to nd the most suitable plan, including the islands to start with,
to end with, and to stop by, such that the king will have the most number of pizzas.
The first line of the input le contains an integer T (1 ≤ T ≤ 50) indicating the number of test cases.
For each test case, the first line contains one integer n (2 ≤ n ≤ 60000). The second line contains n integers, and the i-th number indicates the deliciousness number of the
most favorite pizza of the i-th island. These n numbers are a permutation from 1 to n. Each of the next n - 1 lines contains two integers xi, yi denoting a bridge connecting island xi and island yi.
For each test case please output the number of pizzas that the king can eat.
2 4 1 2 3 4 1 3 2 3 4 3 9 8 5 3 7 9 4 2 6 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
3 5
Migrated from old NTUJ.
tmt514
| No. | Testdata Range | Score |
|---|