  Learn Tech Skills from Scratch @ Scaler EDGE # Delete Edge!

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 109 + 7.

NOTE:

• The tree is rooted at node labeled with 1.

Problem Constraints

2 <= N <= 105

1 <= A[i] <= 103

Input Format

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.

Output Format

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 109 + 7.

Example Input

Input 1:

``` A = [10, 5, 12, 6]
B = [
[1, 2]
[1, 4]
[4, 3]
]
```

Input 2:

``` A = [11, 12]
B = [
[1, 2]
]
```

Example Output

Output 1:

` 270`

Output 2:

``` 132
```

Example Explanation

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 + A) * (A + A) = 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) * (A) = 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. Hints
• Hint 1
• Solution Approach
• Complete Solution