Sum of Path Products in a Binary Tree with Depth Limit

You are given a binary tree with N nodes. Each node has an integer value. The tree is given in level‐order, and the structure is provided by N-1 edges. Additionally, you are given a depth limit D. Your task is to calculate the sum of the products of all paths from the root (node 1) to each leaf, considering only those paths whose depth (i.e. the number of edges from the root) is at most D.

A path product is defined as the product of the node values along that path. Formally, for a path with nodes having values \(a_1, a_2, \dots, a_k\), the product is \(a_1 \times a_2 \times \cdots \times a_k\). You should output the sum of these products for all valid root-to-leaf paths.

Note: If a node has children that would exceed the depth limit, then that node is treated as a leaf and its current path product is included in the sum.

inputFormat

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

1. The first line contains two integers N and D, where N is the number of nodes in the tree, and D is the depth limit.
2. The second line contains N integers, representing the node values in level-order (the first value corresponds to node 1, the root).
3. The following N-1 lines each contain two integers u and v indicating that there is an edge between nodes u and v.

outputFormat

Output to standard output (stdout) a single integer: the sum of the products of all valid root-to-leaf paths whose depth is less than or equal to D.

5 3
1 2 3 4 5
1 2
1 3
2 4
3 5

23