package hackerrank;

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

/**
 * 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) {
        // TODO
        return 0;
    }

    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));
        }
    }
}

@@ -64,24 +64,50 @@
 il.HashMap;%0A
+import java.util.HashSet;%0A
 import java.
@@ -113,24 +113,24 @@
 .util.List;%0A
-
 import java.
@@ -164,16 +164,38 @@
 Scanner;
+%0Aimport java.util.Set;
 %0A%0A/**%0A *
@@ -580,27 +580,997 @@
 List
-) %7B%0A        // TODO
+, Map%3CInteger, Vertex%3E vertices) %7B%0A        int min = Integer.MAX_VALUE;%0A        for (int i = 1; i %3C= adjList.size(); i++) %7B%0A            for (Vertex vertex : adjList.get(i)) %7B%0A                Set%3CInteger%3E marked = new HashSet%3C%3E();%0A                marked.add(vertex.vertex);%0A                int total1 = calcTotalValue(adjList, vertices.get(i), marked);%0A                int total2 = calcTotalValue(adjList, vertex, marked);%0A                int diff = Math.abs(total1 - total2);%0A                min = Math.min(min, diff);%0A            %7D%0A        %7D%0A        return min;%0A    %7D%0A%0A    private static int calcTotalValue(Map%3CInteger, List%3CVertex%3E%3E adjList, Vertex vertex,%0A                                      Set%3CInteger%3E marked) %7B%0A        marked.add(vertex.vertex);%0A        int totalValue = vertex.value;%0A        for (Vertex adj : adjList.get(vertex.vertex)) %7B%0A            if (!marked.contains(adj.vertex)) %7B%0A                totalValue += calcTotalValue(adjList, adj, marked);%0A            %7D%0A        %7D
 %0A   
@@ -1585,9 +1585,18 @@
 urn 
-0
+totalValue
 ;%0A  
@@ -2192,22 +2192,134 @@
 ));%0A        
-%7D
+    adjList.get(to).add(vertices.get(from));%0A        %7D%0A        System.out.println(cutTheTree(adjList, vertices));
 %0A    %7D%0A%7D%0A

Update Cut The Tree