Cerinta completa

There is an undirected tree where each vertex is numbered from to , and each contains a data value. The sum of a tree is the sum of all its nodes’ data values. If an edge is cut, two smaller trees are formed. The difference between two trees is the absolute value of the difference in their sums.

Given a tree, determine which edge to cut so that the resulting trees have a minimal difference between them, then return that difference.

Example

In this case, node numbers match their weights for convenience. The graph is shown below.

image

The values are calculated as follows: 

Edge    Tree 1  Tree 2  Absolute
Cut     Sum      Sum     Difference
1        8         13         5
2        9         12         3
3        6         15         9
4        4         17        13
5        5         16        11

The minimum absolute difference is .

Note: The given tree is always rooted at vertex .

Function Description

Complete the cutTheTree function in the editor below.

cutTheTree has the following parameter(s):

  • int data[n]: an array of integers that represent node values
  • int edges[n-1][2]: an 2 dimensional array of integer pairs where each pair represents nodes connected by the edge

Returns

  • int: the minimum achievable absolute difference of tree sums

Input Format

The first line contains an integer , the number of vertices in the tree.
The second line contains space-separated integers, where each integer denotes the data value, .
Each of the subsequent lines contains two space-separated integers and that describe edge in tree .

Constraints

  • , where .

Sample Input

STDIN                       Function
-----                       --------
6                           data[] size n = 6
100 200 100 500 100 600     data = [100, 200, 100, 500, 100, 600]
1 2                         edges = [[1, 2], [2, 3], [2, 5], [4, 5], [5, 6]]
2 3
2 5
4 5
5 6

Sample Output

400

Explanation

We can visualize the initial, uncut tree as:

cut-the-tree.png

There are edges we can cut:

  1. Edge results in
  2. Edge results in
  3. Edge results in
  4. Edge results in
  5. Edge results in

The minimum difference is .

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    public static Integer[] data;
    public static Integer[] cache;
    public static Integer[] parent;
    public static boolean[] visited;
    public static ArrayList<ArrayList<Integer>> children;

    public static int dfs(int s) {
        int counter = cache[s];
        if (!visited[s]) {
            visited[s] = true;
            for (int i = 0; i < children.get(s).size(); i++) {
                int child = children.get(s).get(i);
                if (!visited[child]) {
                    counter += dfs(child);
                }
            }
            cache[s] = counter;
        }
        return counter;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        data = new Integer[n];
        parent = new Integer[n];
        cache = new Integer[n];
        visited = new boolean[n];
        children = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < n; i++) {
            data[i] = sc.nextInt();
            cache[i] = data[i];
            children.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            u--;
            int v = sc.nextInt();
            v--;
            children.get(u).add(v);
            children.get(v).add(u);
        }

        dfs(0);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            min = Math.min(min, Math.abs(cache[0] - cache[i] - cache[i]));
        }

        System.out.println(min);
    }
}

Scor obtinut: 1.0

Submission ID: 464604141

Link challenge: https://www.hackerrank.com/challenges/cut-the-tree/problem

Cut the Tree