package hackerrank;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * https://www.hackerrank.com/challenges/cut-the-tree
 */
public class CutTheTree {
    private static class Vertex {
        private final int vertex;
        private final int value;

        public Vertex(int vertex, int value) {
            this.vertex = vertex;
            this.value = value;
        }
    }

    private static int cutTheTree(Map<Integer, List<Vertex>> adjList, Map<Integer, Vertex> vertices) {
        int min = Integer.MAX_VALUE;
        // TODO
        for (int i = 1; i <= adjList.size(); i++) {
            for (Vertex vertex : adjList.get(i)) {
                Set<Integer> marked1 = new HashSet<>();
                marked1.add(vertex.vertex);
                int total1 = calcTotalValue(adjList, vertices.get(i), marked1);

                Set<Integer> marked2 = new HashSet<>();
                marked2.add(vertices.get(i).vertex);
                int total2 = calcTotalValue(adjList, vertex, marked2);

                int diff = Math.abs(total1 - total2);
                min = Math.min(min, diff);
            }
        }
        return min;
    }

    private static int calcTotalValue(Map<Integer, List<Vertex>> adjList, Vertex vertex,
                                      Set<Integer> marked) {
        marked.add(vertex.vertex);
        int totalValue = vertex.value;
        for (Vertex adj : adjList.get(vertex.vertex)) {
            if (!marked.contains(adj.vertex)) {
                totalValue += calcTotalValue(adjList, adj, marked);
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Map<Integer, Vertex> vertices = new HashMap<>();
        Map<Integer, List<Vertex>> adjList = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            int val = in.nextInt();
            vertices.put(i, new Vertex(i, val));
            adjList.put(i, new ArrayList<>());
        }
        for (int i = 1; i <= n - 1; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            adjList.get(from).add(vertices.get(to));
            adjList.get(to).add(vertices.get(from));
        }
        System.out.println(cutTheTree(adjList, vertices));
    }
}

@@ -376,16 +376,48 @@
 t value;
+%0A        private int totalValue;
 %0A%0A      
@@ -613,326 +613,170 @@
 ist,
- Map%3CInteger, Vertex%3E vertices) %7B%0A        int min = Integer.MAX_VALUE;%0A        // TODO%0A        for (int i = 1; i %3C= adjList.size(); i++) %7B%0A            for (
+%0A                                  Map%3CInteger, 
 Vertex
+%3E
  vert
-ex : adjList.get(i)) %7B%0A                Set%3CInteger%3E marked1 = new HashSet%3C%3E();%0A                marked1.add(vertex.vertex);%0A                int total1 =
+ices,%0A                                  int totalValue) %7B%0A        int min = Integer.MAX_VALUE;%0A       
  cal
@@ -813,107 +813,125 @@
 get(
-i), marked1);%0A%0A                Set%3CInteger%3E marked2 = new HashSet%3C%3E();%0A                marked2.add(
+1), new HashSet%3C%3E()); // start from the root%0A        for (int i = 2; i %3C= adjList.size(); i++) %7B%0A            int a = 
 vert
@@ -942,29 +942,28 @@
 .get(i).
-vertex);%0A    
+totalValue;%0A
         
@@ -974,64 +974,28 @@
 int 
-total2 = calcTotalValue(adjList, vertex, marked2);%0A%0A    
+b = totalValue - a;%0A
     
@@ -1026,30 +1026,16 @@
 abs(
-total1 - total2);%0A    
+a - b);%0A
     
@@ -1069,30 +1069,16 @@
  diff);%0A
-            %7D%0A
         
@@ -1518,32 +1518,72 @@
     %7D%0A        %7D%0A
+        vertex.totalValue = totalValue;%0A
         return t
@@ -1831,32 +1831,60 @@
 ew HashMap%3C%3E();%0A
+        int totalValue = 0;%0A
         for (int
@@ -2034,24 +2034,55 @@
 yList%3C%3E());%0A
+            totalValue += val;%0A
         %7D%0A  
@@ -2365,16 +2365,28 @@
 vertices
+, totalValue
 ));%0A    

Solve Cut The Tree