Swiggy OA SDE Intern + Fulltime + Fresher + Experienced | CTC - 15 to 30 L | Set 3

Question

Question 2: Recursive Land Division

Problem Statement

A country consists of N regions, each containing a specific number of towns. The government has decided to split the country into two separate nations in a way that minimizes the absolute difference between the total number of towns in each new nation. Each region is connected to another region through roads, forming a tree structure (i.e., an undirected connected graph with N-1 edges and no cycles).

Your task is to determine the minimum possible absolute difference in the number of towns between the two new nations after removing exactly one road.

Input Format

 * The first line contains one integer, N (the number of regions).

 * The second line contains N space-separated integers representing the towns array (number of towns in the i^{th} region).

 * The next N-1 lines each contain two integers, u and v, representing a bidirectional road between regions u and v.

Output Format

 * A single integer representing the minimum possible absolute difference in the number of towns between the two new nations.

Constraints

 * 2 \le N \le 10^5 (Large number of regions)

 * * * The given graph is a tree.

Sample Input

2

10 20

1 2

 

Sample Output

10

 

Explanation

The country has 2 regions connected by a single road: 1-2.

The total number of towns is 10 + 20 = 30.

Possible splits:

 * Removing edge (1,2): Two nations \rightarrow \{10\} and \{20\} \rightarrow |10 - 20| = 10.

   The minimum possible difference is 10.