如何通过移除边将一棵树切成两半？

Question

我的目标是从给定树 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，即树中的顶点数。
下一行将包含由单个 space 分隔的 N 个整数，即分配给每个顶点的值。
接下来的 N−1 行包含一对整数，每行由一个 space 分隔，表示树的边。

在上面的输入中，顶点从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

示例输出

我的密码是

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

我的代码对于较小的输入工作正常；对于上述输入，输出为

而预期的输出是

有什么建议吗？

注意 - 这是家庭作业

Answer 1

您需要添加一种方法来断开子节点与父节点的连接。那看起来像这样：

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

然后您可以从 disconnect() 方法调用此方法，如下所示：

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

}

如何通过移除边将一棵树切成两半？

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

java

tree

graph

data-structures

edge-list