fork download 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static long[] subtree;
  6.     static int[] b;
  7.  
  8.     static void DFS(int node, int parent, List<Integer>[] G) {
  9.  
  10.         subtree[node] = b[node];
  11.  
  12.         for (int child : G[node]) {
  13.  
  14.             if (child == parent) {
  15.                 continue;
  16.             }
  17.  
  18.             DFS(child, node, G);
  19.  
  20.             subtree[node] += subtree[child];
  21.         }
  22.     }
  23.  
  24.     public static void main(String[] args) {
  25.  
  26.         Scanner scanner = new Scanner(System.in);
  27.  
  28.         int n = scanner.nextInt();
  29.  
  30.         b = new int[n + 1];
  31.         subtree = new long[n + 1];
  32.  
  33.         for (int i = 1; i <= n; i++) {
  34.             b[i] = scanner.nextInt();
  35.         }
  36.  
  37.         List<Integer>[] G = new List[n + 1];
  38.  
  39.         for (int i = 1; i <= n; i++) {
  40.             G[i] = new ArrayList<>();
  41.         }
  42.  
  43.         for (int i = 0; i < n - 1; i++) {
  44.  
  45.             int u = scanner.nextInt();
  46.             int v = scanner.nextInt();
  47.  
  48.             G[u].add(v);
  49.             G[v].add(u);
  50.         }
  51.  
  52.         // Root tree at 1
  53.         DFS(1, 0, G);
  54.  
  55.         long total = subtree[1];
  56.  
  57.         long answer = Long.MAX_VALUE;
  58.  
  59.         // Cut the edge parent[i] -- i
  60.         // i.e. consider every non-root node
  61.         // visualise nodes and understand .. node[1] is total sum 
  62.         // node 2 will have only subtree[2] sum and none of node[1](root) and its
  63.         // other child subtree's sum
  64.         for (int i = 2; i <= n; i++) {
  65.  
  66.             long part1 = subtree[i];
  67.             long part2 = total - subtree[i];
  68.  
  69.             long difference = Math.abs(part1 - part2);
  70.  
  71.             answer = Math.min(answer, difference);
  72.         }
  73.  
  74.         System.out.println(answer);
  75.     }
  76. }
Success #stdin #stdout 0.11s 54504KB
comments (?)
stdin 
5
10 5 8 2 6
1 2
1 3
2 4
2 5
stdout 
5
https://ideone.com/ovL7uB
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!