Как я могу разрезать дерево на две части, удалив ребро?

Моя цель состоит в том, чтобы удаление ребра из данного дерева T привело к образованию двух отдельных деревьев, T1 и T2.

Каждой вершине дерева T ставится в соответствие положительное целое число. Моя задача — удалить ребро так, чтобы Tree_diff результирующих деревьев был минимизирован. Tree_diff определяется следующим образом:

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

Формат ввода:

• В первой строке будет целое число N, т.е. количество вершин в дереве.
• В следующей строке будет записано N целых чисел, разделенных одним пробелом, то есть значения, присвоенные каждой из вершин.
• Следующие N−1 строк содержат по паре целых чисел, разделенных одним пробелом, которые обозначают ребра дерева.

В приведенном выше вводе вершины пронумерованы от 1 до N.

Выходной формат: одна строка, содержащая минимальное значение Tree_diff.

Ограничения:

• 3≤N≤105
• 1≤ число, записанное на каждой вершине ≤1001

Образец ввода

50
716 365 206 641 841 585 801 645 208 924 920 286 554 832 359 836 247 959 31 322 709 860 890 195 575 905 314 41 669 549 950 736 265 507 729 457 91 529 102 650 805 373 287 710 556 645 546 154 956 928
14 25
25 13
13 20
20 24
43 2
2 48
48 42
42 5
27 18
18 30
30 7
7 36
37 9
9 23
23 49
49 15
31 26
26 29
29 50
50 21
41 45
45 10
10 17
17 34
28 47
47 44
44 11
11 16
3 8
8 39
39 38
38 22
19 32
32 12
12 40
40 46
1 35
35 4
4 33
33 6
25 2
2 27
7 37
15 50
21 10
17 28
16 39
38 19
40 1

Пример вывода

525

Мой код

import java.util.*;

class Solution{

private static int N;
private static ArrayList<Node> nodes;
public static int count=10000;
public static int count1=0;

private static class Node {
    private Node parent;
    private ArrayList<Node> children;
    private int ID;
    private int value;

    private Node() {
        parent = null;
        ID=0;
        value=0;
        children = new ArrayList<Node>(100);
    }

    private void disconnectChild(Node child) 
    {
        children.remove(child);
    }

    private void disconnect() 
    {   
        if (parent != null)
        {
            parent.disconnectChild(this);
            parent = null;
        }
    }

}

public static void main( String args[] ) 
{
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    nodes = new ArrayList<Node>(N);

    for(int i = 0; i < N; i++) 
        nodes.add(new Node());

    for(int i = 0; i < N; i++) 
    {
        nodes.get(i).ID=i+1;
        nodes.get(i).value = in.nextInt();
    }

    //construct the graph
    for(int i = 0; i < N-1; i++) 
    {
        int first = in.nextInt() - 1;
        int second = in.nextInt() - 1;

        if(nodes.get(second).parent == null)
        {
            nodes.get(first).children.add(nodes.get(second)); 
            nodes.get(second).parent = nodes.get(first);      
        }

        else
        {
            nodes.get(second).children.add(nodes.get(first)); 
            nodes.get(first).parent = nodes.get(second);      
        }

    }

    for(int i=0;i<N;i++)
   {    

        if(nodes.get(i).parent !=  null)
        {
            Node x1 = nodes.get(i);

            while(x1.parent != null)
            {
                x1 = x1.parent;    
            }

            count1 =0;
            calculate(x1);
            int m =count1;

            int a = nodes.get(i).ID;
            int b = nodes.get(i).parent.ID;

            nodes.get(i).disconnect();

            count1 =0;
            calculate(nodes.get(a-1));
            int x = count1;                                
            int y = m - x;
            int z = Math.abs(x-y);

            nodes.get(b-1).children.add(nodes.get(a-1));
            nodes.get(a-1).parent = nodes.get(b-1);

            if(z<count)
                count = z;

        }

   }     
    System.out.println(count);
}

public static void print(Node node)
{
    if(node.children.size()!=0)
    {
        for(int i=0;i<node.children.size();i++)
               print(node.children.get(i));
    }
  System.out.print(node.ID+" ");
}

public static void calculate(Node node)
 {
    count1 = count1 + node.value;
    if(node.children.size()!=0)
    {
        for(int i=0;i<node.children.size();i++)
            calculate(node.children.get(i));
    }   
 }
}

Мой код работает правильно для небольших входных данных; для приведенного выше ввода вывод был

0

В то время как ожидаемый результат был

525

Какие-либо предложения?

Примечание: это домашнее задание