cut the tree by removing edges

Question :- 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. Your 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 eah, 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

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 input's for the above input output was

where as expected output was

Any Suggestions's??

回答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;
    }

}

回答2:

for anyone interested for a another solution with stack i have written my solution in below link https://www.quora.com/How-can-I-solve-the-cut-the-tree-problem-on-HackerRank/answer/Fatih-Tekin?srid=OJeq . I was not sure to paste my own answer from quora is possible in stackoverflow.