通过去除边缘切割树 [英] cut the tree by removing edges
问题描述
问题： -
从给定树中删除边缘T将导致形成两个单独的树T1和T2。
Question :- removal of an edge from a given tree T will result in the formation of two separate trees, T1 and T2.
每个顶点的树T被分配一个正整数。你的任务是去除一个边，使得所得树的Tree_diff最小化。 Tree_diff定义如下：
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))
输入格式： -
第一行将包含整数N，即树中的顶点数。
下一行将包含由单个空格分隔的N个整数，即分配给每个顶点的值。
下一个N-1行包含一对整数eah，由单个空格分隔，表示树的边。
在上面的输入中，顶点从1到N编号。
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.
输出格式： -
包含Tree_diff最小值的单行。
Output Format:- A single line containing the minimum value of Tree_diff.
约束条件： -
3≤N≤105
1≤写在每个顶点的数字≤1001
Constraints :- 3≤N≤105 1≤ number written on each vertex ≤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));
}
}
}
我的代码正常工作以上投入产出的较小投入是
My code is working properly for smaller input's for the above input output was
0
其中预期的输出为
525
任何建议的
推荐答案
您需要添加一个方法来断开子节点与父节点的连接。这将是这样的：
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);
}
然后您可以从断开连接（ ）如下：
private void disconnect()
{
if (parent != null)
{
parent.disconnectChild(this);
parent = null;
}
}
这篇关于通过去除边缘切割树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
