Entering edit mode

You are given an undirected tree with I nodes. Each node of the tree is assigned a

value You are required to divide the nodes into as little groups as possible, such that

no two nodes in a group are adjacent to each other.

Consider a group G. Let us consider a pair(u, w) from the group. The value of the

pair (u, v) is given as |Au - Av| where A, is value assigned to node x

(1 ≤ x ≤ N). The cost of group G is defined as the maximum sum that you can get

by pairing up the nodes of G. Each node can be used only once to make a pair. It is

possible for some nodes in G to be unpaired.

Find the sum of costs of all possible groups that can be made for the given tree.

**Input format**

• The first line has an integer I denoting the number of test cases.

• The first line of each test case contains an integer N denoting the number of

nodes.

• The second line of each test case contains N space-separated integers

denoting the value assigned to the nodes A1, A2, ..., An

• Next N - 1 lines of each test case contain two integers U and V denoting an

edge between the nodes U and V

**Output format**

For each test case, print an integer denoting the sum in a new line.

**Constraints**

1 ≤ T ≤ 10

1 ≤ N ≤ 10^{5}

1 ≤ A[i] ≤10^{9}

1≤ U,V ≤ N

```
Sample Input
1
5
12 17 14 13 16
1 2
1 3
1 5
2 4
Sample Output
4
```

**Explanation**

G1: Nodes 1 and 4 can be grouped together. The cost of the group G'1 turns out to be |12 - 13| = 1, by pairing nodes 1 and 4.G2: Nodes 2, 3, and 5 can be grouped together.Pairing Node 2 and 3, we get value as |17 - 14| = 3. Node 5 is left unpaired.Pairing Node 3 and 5, we get value as |14 - 16 = 2. Node 2 Is left unpaired.Pairing Node 2 and 5, we get value as |17 - 16] = 1. Node 3 is left unpaired.The cost of the group G2 turns out to be 3.

The final answer is cost(G1) + cost(G2) = 4

You are given three arrays A. B, and C of length N.For each index i, A[i] is greater than or equal to B[i].You can perform the given operation on this array A as many

times as you want. In each operation:

• Pick any two indices i and j and add 1 to A[i] and subtract 1

from A[j]. This operation can only be done only if A[j] is

currently greater than B[j]. The cost of this single operation

is C[j].

Note: 1 based indexing is used

**Task**

If you perform the operations optimally, determine the maximum possible minimum number present in the final array.A and also find the minimum cost required to make this possible.As this cost can be very large, you are supposed to find it modulo 10^{9 }+ 7.

**Example**

Assumptions

• N= 5

• A = [1,2,2,3,3,1]

• B = [1,2,1,2,1]

• C = [1,2,1,4,3]

Approach

• The only optimal approach is to choose index as i and index 5 as J and perform the operation on them.

•The array A after that will be [2, 2, 2, 3, 2].

• The maximum possible minimum number in array A is 2. The minimum cost required to do so is C[5] = 3.

• So, the required answer is [2,3]

**Function description**

Complete the solve function provided in the editor. The function takes the following 4 parameters and returns the required answer:

• N: Represents an integer denoting the size of the arrays A,B and C

• A Represents the array of integers A

• B: Represents the array of integers B

• C: Represents the array of integers C

**Input format**

**Note:** This is the input format that you must use to provide custom

input (available above the Compile and Test button).

• The first line contains an integer T denoting the number of test cases.

• The first line contains a single integer ~ denoting the size of the array

• The second line contains N space: separated integers denoting the elements

of the array A

• The third line contains N space-separated integers denoting the elements of the

array B.

• The fourth line contains N space- separated integers denoting the elements

of the array C.

**Output Format**

For each test case in a new line, print the maximum value of the minimum element present in array A and the minimum cost to make it possible modulo 10^{9}+7,

in a space-separated format.

**Constraints**

1<=T <=10^{5}

1<=N < =10^{5 }

1<=A[i],B[i],C[i]<=10^{9}

Sum of N over all testcases < =10^{5 }

```
Sample Input
1
4
1 99 2 9
1 97 2 98
1 5 2 2
Sample output
3 12
```

**Explanation**

The first line contains the number of test cases. T = 1

**For test case 1**

Given

•N=4

• A = [1, 99, 2, 99]

• B = [1, 97, 2, 98]

• C = [1, 5, 2, 2]

**Approach**

• Choose i = 1,j = 2, two times and subtract 2 from 2nd Index element and add 2 in Ist index with cost 5'2 =10

• Choose i = 3, J = 4 subtract 1 from 4th index element and add fin 2nd index element with cost 2.

•After thet, the final array A will be [3, 97 3, 98].You cannot increase the value of the minimum element present in array A any more.The total cost is 12 and the maximum possible minimum value is 3 Hence, the final answer is equal to [3,12].

```
Sample Input
10
10
59 95 8 14 35 13 63 70 15 17
48 47 7 7 5 9 62 43 12 9
61 66 68 89 3 57 71 4 27 9
10
61 61 72 25 45 77 96 100 69 8
55 53 21 24 1 65 79 93 31 3
91 18 40 16 49 18 78 62 52 77
10
61 99 88 3 76 89 20 97 59 50
40 37 82 3 7 13 3 60 17 10
42 15 13 8 51 14 17 4 41 67
10
48 65 39 29 89 18 10 25 89 21
Sample Output
31 1827
53 3894
62 1763
37 4812
58 6384
49 3507
37 4695
61 3485
37 6370
57 4420
```

Loading Similar Posts

In the question 1 of forming groups there are only two groups possible for every tree. Am I right??