**Problem Description**

Given a undirected tree with **N** nodes labeled from **1** to **N**.

Each node has a certain weight assigned to it given by an integer array **A** of size **N**.

You need to delete an edge in such a way that **Product** between sum of weight of nodes in one subtree with sum of weight of nodes in other subtree is **maximized**.

Return this maximum possible product modulo **10 ^{9} + 7**.

**NOTE:**

- The tree is rooted at node labeled with 1.

2 <= N <= 10^{5}

1 <= A[i] <= 10^{3}

First argument is an integer array **A** of size **N** denoting the weight of each node.

Second argument is a 2-D array **B** of size **(N-1) x 2** denoting the edge of the tree.

Return a single integer denoting the maximum product prossible of sum of weights of nodes in the two subtrees formed by deleting an edge with modulo **10 ^{9} + 7**.

Input 1:

A = [10, 5, 12, 6] B = [

[1, 2] [1, 4] [4, 3] ]

Input 2:

A = [11, 12] B = [

[1, 2] ]

Output 1:

270

Output 2:

132

Explanation 1:

Removing edge (1, 4) created two subtrees. Subtree-1 contains nodes (1, 2) and Subtree-2 contains nodes (3, 4) So product will be = (A[1] + A[2]) * (A[3] + A[4]) = 15 * 18 = 270

Explanation 2:

Removing edge (1, 2) created two subtrees. Subtree-1 contains node (1) and Subtree-2 contains node (3) So product will be = (A[1]) * (A[2]) = 11 * 12 = 132

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

Sign Up

to access hints and editorial solutions for**Delete Edge!**

to access hints and editorial solutions for

Loading...