Minimum Time to Zero Health in a Tree

You are given a tree with N nodes (numbered 1 through N) and N-1 edges, forming a connected acyclic graph. Each node i has an initial health value h_i. Additionally, you are given an integer constant d, which represents the amount of time required to reduce 1 unit of health from any node.

To bring a node's health to zero, you need h_i \times d time. Since the health of each node decreases independently, the minimum time required for all nodes to reach zero health is determined by the node that requires the longest time, i.e., the maximum value of h_i \times d over all nodes.

Your task is to compute this minimum time.

Note: Although a tree structure is provided, the answer depends solely on the maximum health value among the nodes.

inputFormat

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

• The first line contains two integers N and d where 1 ≤ N ≤ 10⁵ and 1 ≤ d ≤ 10⁹.
• The second line contains N integers, where the i-th integer denotes the health value of node i (1 ≤ h_i ≤ 10⁹).
• The next N-1 lines each contain two integers u and v indicating an edge between nodes u and v.

outputFormat

Output a single integer representing the minimum time required for all nodes to reach zero health, which is computed as the product of d and the maximum health among all nodes.

5 2
7 3 5 1 9
1 2
1 3
2 4
2 5

18