私の目標は、特定のツリー T からエッジを削除すると、2 つの別個のツリー 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 つのスペースで区切られた整数のペアが含まれており、ツリーのエッジを示しています。
上記の入力では、頂点には 1 から N までの番号が付けられています。
出力形式: Tree_diff の最小値を含む 1 行。
制約:
- 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
助言がありますか？
注意 - これは宿題です