How can I cut a tree into two by removing an edge?

Question

My goal is for 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. My 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 each, 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

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

Sample Output

525

My code is

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

My code is working properly for smaller inputs; for the above input, the output was

0

Whereas the expected output was

525

Any suggestions?

NB - This is a homework assignment

Answer 1

You need to add a method for disconnecting a child from a parent node. That would look something like this:

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

You would then call this method from your disconnect() method like so:

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

}