Problem Statement

Atul is into graph theory, and he is learning about trees nowadays. He observed that the removal of an edge from a given tree T will result in the formation of two separate trees, T1 and T2.

Each vertex of the tree T is assigned a positive integer. Your task is to remove an edge, such that the Tree_diff of the resultant trees is minimized. Tree_diff is defined as the following:

 F(T) = Sum of numbers written on each vertex of a tree T
 Tree_diff(T) = abs(F(T1) - F(T2))

Input Format:
The first line will contain an integer N, i.e. the number of vertices in the tree.
The next line will contain N integers separated by a single space, i.e. the values assigned to each of the vertices.
The next N−1 lines contain a pair of integers eah, separated by a single space, that denote the edges of the tree.
In the above input, the vertices are numbered from 1 to N.

Output Format:
A single line containing the minimum value of Tree_diff.

Constraints:
3≤N≤105
1≤ number written on each vertex ≤1001

Sample Input:
6
100 200 100 500 100 600
1 2
2 3
2 5
4 5
5 6

Sample Output:
400

Explanation:

Originally, we can represent tree as

         1(100)

           2(200)
          /
    (100)5   3(100)
        /
  (500)4   6(600)
Cutting the edge at 1 2 would result in Tree_diff = 1500-100 = 1400
Cutting the edge at 2 3 would result in Tree_diff = 1500-100 = 1400
Cutting the edge at 2 5 would result in Tree_diff = 1200-400 = 800
Cutting the edge at 4 5 would result in Tree_diff = 1100-500 = 600
Cutting the edge at 5 6 would result in Tree_diff = 1000-600 = 400

Hence, the answer is 400.

def find_sum(v, p):
    s = vertices[v-1]
    stack  = [(v,p)]
    while stack:
        v,p = stack.pop()
        for e in adj_list[v]:
            if p != e:
                s += vertices[e-1]
                stack.append((e,v))
    return s

n = int(raw_input())
vertices = map(int, raw_input().split())
adj_list = {}
edges = []
total = sum(vertices)
res = total
for _ in xrange(n-1):
    u, v = map(int, raw_input().split())
    edges.append((u,v))
    if u not in adj_list:
        adj_list[u] = []
    if v not in adj_list:
        adj_list[v] = []
    adj_list[v].append(u)
    adj_list[u].append(v)

for u,v in edges:
    tmp = find_sum(u,v)
    res = min(res, abs(tmp-abs(total-tmp)))
print res