11581158 SUSTech Online Judge
Problem 1158 --Hong set [Hard]

1158: Hong set [Hard]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 127  Solved: 37
[Submit][Status][Web Board]

Description

Hong has a tree, whose vertices are conveniently labeled by 1, 2, ..., n. Each node has a weight wi.

A set with m nodes v1, v2, ..., vm is a Hong Set if:

- The  tree induced by this set is connected.

- After we sort these nodes in set by their weights in ascending order, we get u1, u2, ..., um, (that is, w_ui < w_ui+1 for i from 1 to m-1). For any node x in the path from ui to ui+1(excluding ui and ui+1), should satisfy w_x < w_ui.

Your task is to find the maximum size of Hong Set in a given tree.

Input

The first line will be an integer T (1≤T≤10), which is the number of test cases.  

For each test data:

The first line contains two integers N (1≤N≤200000) — the number of the nodes.

The second line contains N integers w1…wn (1<=wi<=10^9).

Each of the next N - 1 lines contain two integers a and b, which means there is an edge between node a and b.

Output

For each case please print the maximum size of Hong Set.

Sample Input

1
7
3 30 350 100 200 300 400
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output

5

HINT

Source

[Submit][Status]