In this HackerRank Balanced Forest Interview preparation kit problem You need to Complete the balancedForest function. It must return an integer representing the minimum value of c[w] that can be added to allow the creation of a balanced forest, or -1 if it is not possible.

HackerRank Balanced Forest Interview preparation kit solution


Problem solution in Python programming.

from operator import attrgetter
from itertools import groupby
from sys import stderr

class Node:
    def __init__(self, index, value):
        self.index = index
        self.value = value
        self.children = []
        
def readtree():
    size = int(input())
    values = readints()
    assert size == len(values)
    nodes = [Node(i, v) for i, v in enumerate(values)]
    for _ in range(size - 1):
        x, y = readints()
        nodes[x-1].children.append(nodes[y-1])
        nodes[y-1].children.append(nodes[x-1])
    return nodes

def readints():
    return [int(fld) for fld in input().strip().split()]

def findbestbal(nodes):
    if len(nodes) == 1:
        return -1
    rootify(nodes[0])
#    print([(n.index, n.value, n.totalval) for n in nodes], file=stderr)
    best = total = nodes[0].totalval
    dummynode = Node(None, None)
    dummynode.totalval = 0
    sortnode = []
    for k, g in groupby(sorted([dummynode] + nodes, key = attrgetter('totalval')), attrgetter('totalval')):
        sortnode.append(list(g))
    total = nodes[0].totalval
    for ihi, n in enumerate(sortnode):
        if 3 * n[0].totalval >= total:
            break
    else:
        assert False
    ilo = ihi - 1
    for ihi in range(ihi, len(sortnode)):
        hi = sortnode[ihi][0].totalval
        lo = sortnode[ilo][0].totalval
        while 2 * hi + lo > total:
            if lo == 0:
                return -1
            if (total - lo) % 2 == 0:
                x = (total - lo) // 2
                for lonode in sortnode[ilo]:
                    if uptototalval(lonode, x + lo):
                        return x - lo
            ilo -= 1
            lo = sortnode[ilo][0].totalval
        if len(sortnode[ihi]) > 1:
            return 3 * hi - total
        hinode = sortnode[ihi][0]
        if 2 * hi + lo == total:
            for lonode in sortnode[ilo]:
                if uptototalval(lonode, hi) != hinode:
                    return hi - lo
        y = total - 2 * hi
        if uptototalval(hinode, 2 * hi) or uptototalval(hinode, hi + y):
            return hi - y

def rootify(root):
    root.parent = root.jumpup = None
    root.depth = 0
    bfnode = [root]
    i = 0
    while i < len(bfnode):
        node = bfnode[i]
        depth = node.depth + 1
        jumpup = uptodepth(node, depth & (depth - 1))
        for child in node.children:
            child.parent = node
            child.children.remove(node)
            child.depth = depth
            child.jumpup = jumpup
            bfnode.append(child)
        i += 1
    for node in reversed(bfnode):
        node.totalval = node.value + sum(child.totalval for child in node.children)
            
def uptodepth(node, depth):
    while node.depth > depth:
        if node.jumpup.depth <= depth:
            node = node.jumpup
        else:
            node = node.parent
    return node
            
def uptototalval(node, totalval):
  try:
#    print('uptototalval(%s,%s)' % (node.index, totalval), file=stderr)
    while node.totalval < totalval:
        if node.parent is None:
            return None
        if node.jumpup.totalval <= totalval:
            node = node.jumpup
        else:
            node = node.parent
#        print((node.index, node.totalval), file=stderr)
    if node.totalval == totalval:
        return node
    else:
        return None
  except Exception:
    return None
    
ncases = int(input())
for _ in range(ncases):
    print(findbestbal(readtree()))


Problem solution in Java Programming.

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scanner = new Scanner(System.in) ;
        int q = scanner.nextInt() ;
        if (q < 1 || q > 5) {
            throw new IllegalArgumentException("1<=Q<=50000") ;
        }
        while(q>0) {
            int n = scanner.nextInt() ;
            if (n < 1 || n > 50000) {
                throw new IllegalArgumentException("1<=N<=50000") ;
            }
            List<Node> nodes = new ArrayList<Node>(n) ;
			List<GraphNode> graph = new ArrayList<GraphNode>(n) ;
			List<TreeNode> tree = new ArrayList<TreeNode>(n) ;
            for(int i=1;i<=n;i++) {
				Node node = new Node(i,scanner.nextInt()) ;
                nodes.add(node) ;
				graph.add(new GraphNode(node)) ;
				tree.add(new TreeNode(node)) ;
            }
            List<Edge> edges = new ArrayList<Edge>() ;
            for(int i=0;i<n-1;i++) {
                Edge edge = new Edge(scanner.nextInt(), scanner.nextInt()) ;
                edges.add(edge) ;
                addEdge(graph,edge) ;
            }
			graphsToTree(graph.get(0),tree,new HashSet<Node>()) ;
            //System.out.println(tree.get(0)) ;
            //System.out.println(edges) ;
            System.out.println(findMinCw(tree, edges, tree.get(0))) ;
            q-- ;
        }
    }
    
	private static class Node {
		int nodeId ;
        long coins=0 ;
		
		public Node(int nodeId, long coins) {
            this.nodeId = nodeId ;
            this.coins = coins ;
        }
        public int getNodeId() {
            return nodeId ;
        }
        public long getCoins() {
            return coins ;
        }
		
		public boolean equals(Node node) {
            return (node!=null && node.getNodeId() == nodeId) ;
        }
        
        public int hashCode() {
            return nodeId ;
        }
		public String toString() {
			return String.format("nodeId:%s, coins:%d",nodeId,coins) ;
		}
	}
	
	private static class GraphNode {
		
		final Node node ;
		Set<GraphNode> connectedNodes = new HashSet<GraphNode>() ;
		
		public GraphNode(Node node) {
			this.node = node ;
		}
		public Node getNode() {
			return node ;
		}
		public void addConnection(GraphNode addNode) {
			connectedNodes.add(addNode) ;
		}
		public void removeConnection(GraphNode removeNode) {
			connectedNodes.remove(removeNode) ;
		}
		public Set<GraphNode> getConnectedNodes() {
			return connectedNodes ;
		}        
        public String toString() {
			return String.format("Node:%s, connectedNodes[%s]",node.toString(),connectedNodesToString()) ;
        }
		private String connectedNodesToString() {
			StringBuilder builder = new StringBuilder() ;
			for(GraphNode node : connectedNodes) {
				builder.append("Node:").append(node).append(",") ;
			}
			return builder.toString() ;
		}
    }
	
	private static class TreeNode {
		final Node node ;
		TreeNode parentNode ;
		Set<TreeNode> childNodes = new HashSet<TreeNode>() ;
		long totalCoins ;
		
		public TreeNode(Node node) {
			this.node = node ;
			totalCoins = node.getCoins() ;
		}
		public Node getNode() {
			return node ;
		}
		public long getTotalCoins() {
			return totalCoins ;
		}
		public Set<TreeNode> getChildNodes() {
			return childNodes ;
		}
		
		public void setParent(TreeNode node) {
            if(parentNode!=null && node!=null){
                throw new RuntimeException("Multiple parent is not supported. parent:"+parentNode+" current:"+this+" new parent:"+node);
            }
            parentNode = node ;
        }
		
		public void addChildNode(TreeNode node) {
            childNodes.add(node) ;
            totalCoins+=node.getTotalCoins() ;
            node.setParent(this) ;
            if (parentNode!=null) {
                parentNode.addChildCoins(node.getTotalCoins()) ;
            }
        }
		
		public void addChildCoins(long childCoins) {
            totalCoins += childCoins ;
            if (parentNode!=null) {
                parentNode.addChildCoins(childCoins) ;
            }
        }
		
		public void removeChildNode(TreeNode node) {
            childNodes.remove(node) ;
            totalCoins-=node.getTotalCoins() ;
            node.setParent(null) ;
            if (parentNode!=null) {
                parentNode.removeChildCoins(node.getTotalCoins()) ;
            }
        }
		
		public void removeChildCoins(long childCoins) {
            totalCoins -= childCoins ;
            if (parentNode!=null) {
                parentNode.removeChildCoins(childCoins) ;
            }
        }
		
		public boolean isParentOf(TreeNode childNode) {
			return childNodes.contains(childNode) ;
		}
		
		public boolean isRoot() {
			return parentNode == null ;
		}
		
		public String toString() {
			return String.format("Node:%s, totalCoins:%d, parentNode:%s, childNodes:[%s]",node.toString(), totalCoins, 
				(parentNode!=null)?parentNode.getNode().toString():"NULL",childNodes.toString()) ;
		}
	}
	
    private static class Edge {
        int node1 ;
        int node2 ;
        
        public Edge(int node1, int node2) {
			this.node1 = node1 ;
			this.node2 = node2 ;
        }

		public int getNode1() {
			return node1 ;
		}

		public int getNode2() {
			return node2 ;
		}
        
		public void swapNode() {
			int tmpNode = node1 ;
			node1 = node2 ;
			node2 = tmpNode ;
		}
		
        public String toString() {
            return "node1:"+node1+" node2:"+node2 ;
        }
    }
    
    private static void addEdge(List<GraphNode> nodes, Edge edge) {
        nodes.get(edge.getNode1()-1).addConnection(nodes.get(edge.getNode2()-1)) ;
        nodes.get(edge.getNode2()-1).addConnection(nodes.get(edge.getNode1()-1)) ;
    }
    
    private static void removeEdge(List<GraphNode> nodes, Edge edge) {
        nodes.get(edge.getNode1()-1).removeConnection(nodes.get(edge.getNode2()-1)) ;
        nodes.get(edge.getNode2()-1).removeConnection(nodes.get(edge.getNode1()-1)) ;
    }
	
	private static void graphsToTree(GraphNode graph, List<TreeNode> treeNodes, Set<Node> visitedNode) {
		TreeNode treeNode = treeNodes.get(graph.getNode().getNodeId()-1) ;
		visitedNode.add(graph.getNode()) ;
		for(GraphNode connectedNode : graph.getConnectedNodes()) {
			if (!visitedNode.contains(connectedNode.getNode())) {
				treeNode.addChildNode(treeNodes.get(connectedNode.getNode().getNodeId()-1)) ;
				visitedNode.add(connectedNode.getNode()) ;
				graphsToTree(connectedNode, treeNodes, visitedNode) ;
			}			
		}
	}
	
	private static TreeNode removeTreeEdge(List<TreeNode> nodes, Edge edge) {
		TreeNode node1 = nodes.get(edge.getNode1()-1) ;
		TreeNode node2 = nodes.get(edge.getNode2()-1) ;
		
		if (node1.isParentOf(node2)) {
			// node1 is parent of node2
			node1.removeChildNode(node2) ;			
			return node2 ;
		} else {
			node2.removeChildNode(node1) ;
			edge.swapNode() ;
			return node1 ;
		}
	}
	
	private static void addTreeEdge(List<TreeNode> nodes, Edge edge, TreeNode rootNode) {
		TreeNode node1 = nodes.get(edge.getNode1()-1) ;
		TreeNode node2 = nodes.get(edge.getNode2()-1) ;
		
		node1.addChildNode(node2) ;	
	}
	
	//DFS on subTree with expected value
	private static boolean findSubTreeWithValue(TreeNode searchRoot, TreeNode tree, long expectedValue) {
		if (searchRoot.getTotalCoins() <= expectedValue || tree.getTotalCoins() <= expectedValue) {
			return false ;
		}
		for(TreeNode subTree : tree.getChildNodes()) {
			long subTreeCoins = subTree.getTotalCoins() ;
			long remainingCoins = searchRoot.getTotalCoins()-subTreeCoins ;
			
			if (subTreeCoins == expectedValue || remainingCoins==expectedValue) {
				return true ;
			}
			if (findSubTreeWithValue(searchRoot,subTree,expectedValue)) {
				return true ;
			}
		}
		return false ;
	}
	
	public static long findMinCw(List<TreeNode> nodes, List<Edge> edges, TreeNode rootNode) {
        long minCw = -1 ;
        for (int i = 0; i<edges.size() ;i++) {
			Edge removeEdge1 = edges.get(i) ;
			TreeNode tree1 = removeTreeEdge(nodes,removeEdge1) ;
            
            long nodes1Coins = rootNode.getTotalCoins() ;
            long nodes2Coins = tree1.getTotalCoins()  ;

            long largeSetCoins, smallSetCoins ;
            TreeNode treeToSplit = null ;
			
            if (nodes1Coins == nodes2Coins) {
                long cw = nodes1Coins ;
                if (minCw <0 || cw < minCw) {
                    minCw = cw ;
                }
				addTreeEdge(nodes, removeEdge1, rootNode);
                continue ;
            } else if (nodes1Coins>nodes2Coins) {
                largeSetCoins = nodes1Coins ;
                smallSetCoins = nodes2Coins ;
				treeToSplit = rootNode ;
            } else {
                largeSetCoins = nodes2Coins ;
                smallSetCoins = nodes1Coins ;                
				treeToSplit = tree1 ;
            }

            long expectedCw = -1 ;
            long expectedCw1 = -1 ;
			long searchValue ;
            if (largeSetCoins%2 == 0) {
                expectedCw1 = largeSetCoins/2l - smallSetCoins ;
            }
            long expectedCw2 = smallSetCoins - (largeSetCoins - smallSetCoins) ;

            if (expectedCw1 >= 0 && expectedCw2 >=0) {
                expectedCw = Math.min(expectedCw1,expectedCw2) ;
            } else if (expectedCw1 >= 0) {
                expectedCw = expectedCw1 ;
            } else if (expectedCw2 >= 0) {
                expectedCw = expectedCw2 ;
            }
            
            if (expectedCw<0 || (minCw >0 && expectedCw > minCw)) {
                addTreeEdge(nodes, removeEdge1, rootNode);
                continue ;
            }

			if (expectedCw == expectedCw1) {
				searchValue = largeSetCoins/2l ;
			} else {
				searchValue = smallSetCoins ;
			}

			if (findSubTreeWithValue(treeToSplit, treeToSplit, searchValue)) {
				if (minCw <0 || expectedCw < minCw) {
                    minCw = expectedCw ;
                }
			}
		
            addTreeEdge(nodes, removeEdge1, rootNode);
        }
        return minCw ;
    }

}


Problem solution in C++ programming.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cassert>
#include <stdlib.h>

using namespace std;


typedef long long ll;

const ll INF = (ll) 1e18;
const int N = (int) 5e4 + 10;

vector<int> g[N];
ll c[N];
ll f[N];
ll res = INF;
ll tot = 0;
bool was[N];

void upd(ll a, ll b, ll c) {
    if (a == b && c <= a)
        res = min(res, a - c);
    if (a == c && b <= a)
        res = min(res, a - b);
    if (b == c && a <= b)
        res = min(res, b - a); 
}

set<ll>* unite(set<ll>* a, set<ll>* b) {
    if (a->size() > b->size())
        swap(a, b);
    for (ll x : *a) {
        if (b->count(tot - 2 * x))
            upd(tot - 2 * x, x, x);
        if (b->count(x))
            upd(x, x, tot - 2 * x);
        if ((tot - x) % 2 == 0 && b->count((tot - x) / 2))
            upd((tot - x) / 2, x, (tot - x) / 2);
    }
    for (ll x : *a) {
        b->insert(x);
    }
    delete a;
    return b;
}

set<ll>* dfs(int v) {
    was[v] = true;
    f[v] = c[v];
    set<ll>* sv = new set<ll>();
    for (int to : g[v])
        if (!was[to]) {
            set<ll>* sto = dfs(to);
            f[v] += f[to];
            sv = unite(sv, sto);
        }
    if (f[v] % 2 == 0 && sv->count(f[v] / 2))
        upd(f[v] / 2, f[v] / 2, tot - f[v]);
    if (sv->count(tot - f[v]))
        upd(tot - f[v], 2 * f[v] - tot, tot - f[v]);
    if (sv->count(2 * f[v] - tot))
        upd(2 * f[v] - tot, tot - f[v], tot - f[v]);
    sv->insert(f[v]);
    return sv;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < N; i++) {
        was[i] = false;
        g[i].clear();
        c[i] = 0;
    }
    tot = 0;
    res = INF;
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        tot += c[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    set<ll>* s = dfs(0);
    //for (int i = 0; i < n; i++)
    //    cerr << f[i] << " ";
    //cerr << endl;
    delete s;
    if (res == INF)
        res = -1;
    cout << res << endl;
    // cerr << "----------" << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    int p;
    cin >> p;
    while (p--) {
        solve();
    }
    return 0;
}


Problem solution in C programming.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

struct Node
{
    int64_t sum; // sum of all node in this tree.
    int64_t testSum;
    int data;
    int parent;
    int *child;
    int childCnt;
};
typedef struct Node Node;

void sumTree(Node *root, int index)
{
    int i;
    root[index].sum = root[index].data;
    for (i = 0; i < root[index].childCnt; i++)
    {
        int child = root[index].child[i];
        if (child == root[index].parent) continue;
        sumTree(root, child);
        root[index].sum += root[child].sum;
    }
    root[index].testSum = root[index].sum;
}

void updateTree(Node *tree, int root, int parent)
{
    tree[root].parent = parent;
    int i;
    for (i = 0; i < tree[root].childCnt; i++)
    {
        if (tree[root].child[i] == parent) continue;
        updateTree(tree, tree[root].child[i], root);
    }
}

int64_t childSum(Node *tree, int root, int  branch_root, int64_t targetSum, bool *bFound)
{
    int i;
    int64_t currSum = 0;

    if (tree[root].testSum < targetSum) return tree[root].testSum;

    for (i = 0; (i < tree[root].childCnt) && (*bFound==0); i++)
    {
        int child = tree[root].child[i];
        if (child == tree[root].parent) continue;
        if (child == branch_root) continue;
        int64_t chSum = childSum(tree, child, branch_root, targetSum, bFound);

        if (chSum == targetSum)
        {
            *bFound = 1;
            break;
        }

        currSum += chSum;
    }
    return currSum + tree[root].data;
}

// Complete the balancedForest function below.
int64_t balancedForest(int c_count, int* c, int edges_rows, int edges_columns, int** edges) {
    int i, j;
    // build tree.
    Node *tree = (Node *)calloc(c_count, sizeof(Node));
    for (i = 0; i < c_count; i++)
    {
        tree[i].data = c[i];
        tree[i].childCnt = 0;
        tree[i].child = NULL;
        tree[i].parent = -1;
        tree[i].sum = 0;
    }
    for (i = 0; i < edges_rows; i++)
    {
        int pa = edges[i][0] - 1;
        int ch = edges[i][1] - 1;
        tree[pa].child = (int *)realloc(tree[pa].child, (1 + tree[pa].childCnt) * sizeof(int));
        tree[pa].child[tree[pa].childCnt] = ch;
        tree[pa].childCnt++;
        tree[ch].child = (int *)realloc(tree[ch].child, (1 + tree[ch].childCnt) * sizeof(int));
        tree[ch].child[tree[ch].childCnt] = pa;
        tree[ch].childCnt++;
    }
    // Now update the parent_node;
    int root = 0; // pick the first one as root.
    updateTree(tree, root, -1);
    sumTree(tree, root);

    int64_t treeSum = 0;
    treeSum = tree[root].sum;
    
    int64_t maxSum = (treeSum - 1) / 2 + 1;
    int64_t minSum = treeSum / 3 - 1;
    int64_t minW = -1;
    for (i = 0; i < c_count; i++)
    {
        if (i == root) continue;

        //if (tree[i].sum >= minSum && tree[i].sum <= maxSum)
        {
            int64_t sumI = tree[i].sum;

            // Check for special case.
            int64_t sumJ = treeSum - sumI;

            if (sumI == sumJ)
            {
                if (minW<0 || minW>sumI) minW = sumI;
            }
            else
            {
                bool bFound = 0;
                int64_t targetSum;
                int searchRoot = root;
                int branchRoot = i;
                int64_t w = 0;
                if (sumI > sumJ)
                {
                    targetSum = sumI;
                    sumI = sumJ;
                    sumJ = targetSum;
                    searchRoot = i;
                    branchRoot = root;
                }
                if ((sumI << 1) < sumJ)
                {
                    targetSum = sumJ >> 1;
                    if (sumJ - targetSum != targetSum) continue;
                    w = targetSum - sumI;
                }
                else
                {
                    targetSum = sumI;
                    w = targetSum - (sumJ - sumI);
                }

                if (minW >= 0 && minW < w) continue;

                // search in the main tree
                
                // first, update the testSum;
                if (searchRoot == root)
                {
                    int curr = tree[branchRoot].parent;
                    int64_t branchSum = tree[branchRoot].sum;
                    while (curr != -1)
                    {
                        tree[curr].testSum -= branchSum;
                        curr = tree[curr].parent;
                    }
                }

                childSum(tree, searchRoot, branchRoot, targetSum, &bFound);
                if (bFound)
                {
                    if (minW == -1 || minW > w) minW = w;
                }

                // last, restore the testSum
                if (searchRoot == root)
                {
                    int curr = tree[branchRoot].parent;
                    while (curr != -1)
                    {
                        tree[curr].testSum = tree[curr].sum;
                        curr = tree[curr].parent;
                    }
                }
            }
        }
    }
    return minW;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* q_endptr;
    char* q_str = readline();
    int q = strtol(q_str, &q_endptr, 10);

    if (q_endptr == q_str || *q_endptr != '\0') { exit(EXIT_FAILURE); }

    for (int q_itr = 0; q_itr < q; q_itr++) {
        char* n_endptr;
        char* n_str = readline();
        int n = strtol(n_str, &n_endptr, 10);

        if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

        char** c_temp = split_string(readline());

        int* c = malloc(n * sizeof(int));

        for (int i = 0; i < n; i++) {
            char* c_item_endptr;
            char* c_item_str = *(c_temp + i);
            int c_item = strtol(c_item_str, &c_item_endptr, 10);

            if (c_item_endptr == c_item_str || *c_item_endptr != '\0') { exit(EXIT_FAILURE); }

            *(c + i) = c_item;
        }

        int c_count = n;

        int** edges = malloc((n - 1) * sizeof(int*));

        for (int i = 0; i < n - 1; i++) {
            *(edges + i) = malloc(2 * (sizeof(int)));

            char** edges_item_temp = split_string(readline());

            for (int j = 0; j < 2; j++) {
                char* edges_item_endptr;
                char* edges_item_str = *(edges_item_temp + j);
                int edges_item = strtol(edges_item_str, &edges_item_endptr, 10);

                if (edges_item_endptr == edges_item_str || *edges_item_endptr != '\0') { exit(EXIT_FAILURE); }

                *(*(edges + i) + j) = edges_item;
            }
        }

        int edges_rows = n - 1;
        int edges_columns = 2;

        int64_t result = balancedForest(c_count, c, edges_rows, edges_columns, edges);

        fprintf(fptr, "%lld\n", result);
    }

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) {
            break;
        }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
            break;
        }

        alloc_length <<= 1;

        data = realloc(data, alloc_length);

        if (!line) {
            break;
        }
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';

        data = realloc(data, data_length);
    } else {
        data = realloc(data, data_length + 1);

        data[data_length] = '\0';
    }

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);

        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}


Problem solution in JavaScript programming.

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the balancedForest function below.
function balancedForest(c, edges) {
    const nodes = c.map(cost => ({ cost, adj: [], visited: false, solved: false }));
    
    for(let [a,b] of edges) {
        nodes[a-1].adj.push(b-1);
        nodes[b-1].adj.push(a-1);
    }
    
    const dfs = n => {
        if (n.visited) return 0;
        n.visited = true;
        
        for (let a of n.adj)
            n.cost += dfs(nodes[a]);
        return n.cost;
    }
    
    const sum = dfs(nodes[0]);
    //console.log(sum, nodes);

    let min = sum;
    const excsum = {};
    const incsum = {};
    
    const solve = n => {
        if (n.solved) return;
        n.solved = true;
        
        const cost_a = 3 * n.cost - sum;
        const cost_b = (sum - n.cost) / 2 - n.cost;
        //console.log("solve", n, { incsum, excsum }, { min, cost_a, cost_b });

        // can split in two equal subtrees?
        if (sum % 2 === 0 && n.cost === (sum / 2)) min = Math.min(min, sum / 2);

        if (cost_a >= 0 && (
            excsum[n.cost] // another subtree with equal cost?
            || excsum[sum - 2 * n.cost] // another subtree with 1/3 cost
            || incsum[sum - n.cost]) // edge to remove
        ) min = Math.min(min, cost_a);

        if (cost_b >= 0 && (sum - n.cost) % 2 === 0) {
            if (excsum[(sum - n.cost) / 2] || incsum[(sum + n.cost) / 2]) 
                min = Math.min(min, cost_b);
        }

        incsum[n.cost] = true;
        for (let a of n.adj) solve(nodes[a]);
        delete incsum[n.cost];
        excsum[n.cost] = true;
    }
    
    solve(nodes[0]);
    return min === sum ? -1 : min;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const q = parseInt(readLine(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const n = parseInt(readLine(), 10);

        const c = readLine().split(' ').map(cTemp => parseInt(cTemp, 10));

        let edges = Array(n - 1);

        for (let i = 0; i < n - 1; i++) {
            edges[i] = readLine().split(' ').map(edgesTemp => parseInt(edgesTemp, 10));
        }

        const result = balancedForest(c, edges);

        ws.write(result + '\n');
    }

    ws.end();
}