Longest Distinct-Node Path in a Binary Tree

You are given a binary tree with N nodes, where each node has an integer value. The tree is constructed using a list of node values and a list of edges. Each edge is given as a pair of integers (u, v), representing an edge from node u to node v. When constructing the tree, assign the first available child (left child first, then right child) for each node.

Your task is to determine the length l of the longest simple downward path starting from the root such that:

• All node values in the path are distinct.
• The sum of the node values along the path does not exceed K, that is, if the path values are \(a_1, a_2, \ldots, a_l\), then \(\sum_{i=1}^{l} a_i \le K\).

Note: The path always starts from the root of the tree and proceeds downward (following child pointers only).

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer T denoting the number of test cases.
2. For each test case:
   1. An integer N representing the number of nodes in the tree.
   2. A line containing N space-separated integers denoting the values of the nodes (nodes are numbered from 1 to N, and the first value corresponds to the root).
   3. N - 1 lines each containing two integers u and v representing an edge from node u to node v. For each node, assign the first child encountered as the left child and the second as the right child.
   4. A single integer K, the maximum allowed sum for a valid path.

outputFormat

For each test case, print a single line to standard output (stdout) containing the length of the longest valid path.

## sample

1
5
10 20 30 40 50
1 2
1 3
2 4
2 5
80

3

</p>