Alice is playing with a tree consisting of N nodes, each with its own unique value. For any two distinct nodes x and y, she wants to compute a special score h(x, y) for each pair. Here’s how she defines it:
Maximum Value on Path f(x, y): This is the highest value among all nodes on the path connecting x and y.
Minimum Value on Path g(x, y): This is the lowest value among all nodes on the same path.
Special Score h(x, y): This is simply the product of f(x, y) and g(x, y), or h(x,y)=f(x,y)*g(x,y)
Alice wants to calculate the total sum of h(x, y) for every unique pair of nodes (x, y) where x ≠ y. Since the result might be huge, give the final answer modulo 1e9 + 7
Input Format The first line contains an integer N denoting the number of nodes in the tree.
The second line contains N space-separated integers A1, A2, ..., AN denoting the values associated with each node.
The next N — 1 lines each contain two integers ui, vi, denoting an edge between nodes ui and vi.
constraints-> 1≤N≤2×10^5
ANY IDEA FOR THIS PROBLEM?
