Last Updated: 26 Sep, 2021

Perfect Partition

Moderate

Asked in company

Solve now

Problem statement

In the Ninja world, assets owned by a person are represented by a tree, where the total asset value is equal to the sum of all its vertices.

A wealthy father wants to split all his assets between his two children, he has appointed you to help him. You are given a tree containing ‘N’ vertices, vertices are numbered from 0 to N-1, you are also given an array ‘Assets’ denoting the asset-value of i^th vertex.

Splitting of assets can simply be done by removing an edge from the tree, this results in the formation of two trees. You have to remove an edge such that the partition is as fair as possible. In a fair partition, the difference between the assets of the children should be as small as possible.

Return the minimum possible difference between the asset values of the children after partition.

For Example :

If N = 5 and Assets = { 10, 20, 30, 40, 50 } and tree is denoted as:

Then we have 4 choices of deletion:
Edge 0-1 is deleted: now, the one of the tree contains node-1 and node-3, and the other contains node-0, node-2 and node-3, subtree difference is = 90 - 60 = 30
Edge 1-3 is deleted: subtree difference is = 110 - 40 = 70
Edge 0-2 is deleted: subtree difference is = 80 - 70 = 10
Edge 2-4 is deleted: subtree difference is = 100 - 50 = 50


Clearly removing the edge between node-0 and node-2 leads to the most optimal partition where the difference is equal to 10. Hence we return the value 10.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the number of assets.

The next line contains N integers, where Assets[i] denotes the asset-value of the ith asset.

The next N-1 lines each contain two integers ‘U’ and ‘V’ denoting that there is an edge between node-U and node-V.

Output Format :

For each test case, print the lowest possible difference between assets after splitting.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10      
2 ≤ N ≤ 200
0 ≤ Assets[i] ≤ 10^6
0 ≤ U, V ≤ N-1

Time limit: 1 sec

Solve now

Approaches

01 Approach

Try to remove the edges one by one to find the optimal partition.

The steps are as follows :

Initialize “total” equal to 0 to store the total sum of all the assets, calculate “total” equal to the sum of all the values in array ‘Assets’.
Initialize “ans” equal to INT_MAX to store the minimum possible difference.
Run a for loop for variable “remove” from 0 to N-1, and run an inner loop for variable “i” from 0 to N-1, Now build an adjacency list each time and don’t include the remove^th node in it. Call DFS function, to sum up the values for one of the partitions, the sum will denote the asset value that child-1 will get, update “ans” if needed.
Finally, return the value of “ans”.

Solve now

02 Approach

Since the total asset value is equal to the sum of the asset values of each node, the ideal partition would be one in which one of the children is given assets as close as half the total asset value. Partition involves splitting the current tree into two trees, hence we simply need to find a subtree that has its sum closest to half of the total assets, we can then simply partition the tree about the edge that connects it with the remaining tree.

To find the optimal subtree we need not have to calculate the sum of each subtree one by one, rather we can use a single depth-first search call and use the precomputed sum to directly find the sum of the subtree more efficiently, that is: the sum of the subtree rooted at i^th node is equal to the sum of the asset value of i^th node and the sum of all the subtrees of children of I.

The steps are as follows :

Initialize “total” equal to 0 to store the total sum of all the assets, and run DFS from the 0^thnode to calculate the total sum of all asset values.
Initialize adjacency list “adj” and store the edge information to apply DFS easily.
Initialize “ans” equal to INT_MAX to store the minimum possible difference.
Initialize an array “vis” to keep the track of visited nodes in DFS.
Make a DFS call from the 0^thnode, and the DFS call returns the sum of Asset[i] and the sum of all the values returned by children of i^thnode, this value is also equal to the sum of the subtree rooted at i^th node.
For each DFS call calculate the difference between asset values of children and update it in “ans” if needed.
Finally, return the value of “ans”.

Solve now

Perfect Partition

Problem statement

In the Ninja world, assets owned by a person are represented by a tree, where the total asset value is equal to the sum of all its vertices.

A wealthy father wants to split all his assets between his two children, he has appointed you to help him. You are given a tree containing ‘N’ vertices, vertices are numbered from 0 to N-1, you are also given an array ‘Assets’ denoting the asset-value of ith vertex.

Splitting of assets can simply be done by removing an edge from the tree, this results in the formation of two trees. You have to remove an edge such that the partition is as fair as possible. In a fair partition, the difference between the assets of the children should be as small as possible.

Return the minimum possible difference between the asset values of the children after partition.

For Example :

Input Format :

Output Format :

Note :

Constraints :

Approaches

01 Approach

02 Approach

A wealthy father wants to split all his assets between his two children, he has appointed you to help him. You are given a tree containing ‘N’ vertices, vertices are numbered from 0 to N-1, you are also given an array ‘Assets’ denoting the asset-value of i^th vertex.