You are given a tree consisting of N nodes and another integer K, where the \(i^{th}\) node has value equal to \(v[i]\).
Now, we call the value of a sub-tree the number of distinct \(v[i]\) among all nodes it contains. You need to find the number of sub-trees of this tree having value \( \le K \) .
A sub-tree of a tree is a subset of nodes and edges of the tree that form a single connected component.
Input: :
Input starts with an integer \( ( 1 \le T \le 15)\) denoting the number of test cases. Each case starts with two positive integers N and K.
The next line consists of N space separated integers, where the \(i^{th}\) integer denotes \(v[i]\). Each of the next \(N-1\) lines contains 2 space separated integers u and v, denoting an edge between nodes u and v,
Output:
For each test case, print the answer on a new line.
Constraints:
\( 1 \le T \le 15 \)
\( 2 \le N \le 18 \)
\( 1 \le K \le N \)
\( 0 \le v[i] \le 10^9 \)
\( 1 \le u,v \le N \)
In the sample test case given there are 9 subtrees that have their value less than or equal to 2 and those can be listed as following -
1.) Subtree with only one node - There are 5 such subtress i.e. all the nodes taken 1 at a time 1,2,3,4,5
2.) Subtree with only two nodes - There are 4 such subtrees i.e. all the edges taken 1 at a time (1,2) , (1,3) , (1,5) and (2,4)
Apart from that any subtree will have its value either greater than 2 or the subtree won't be connected
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor