HackerRank Cut the Tree Problem Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    //idea: accumulate costs bottom up from leaves to root
    //the costs are c1 for one subtree, and totalcost-c1 for the other
    long n;
    long long vvalue[100000]={0}; //stores the value of each vertex    
    scanf("%ld",&n);
    for(long i=0;i<n;i++){scanf("%lld",&vvalue[i]);}
    //needs a good data structure to implement the tree
    long treeedges[n-1][2];
    for (long l=0;l<n-1;l++){
        long i,j;
        scanf("%ld %ld",&i,&j);
        if(i>j) {treeedges[l][0]=j-1;treeedges[l][1]=i-1;}
        else {treeedges[l][0]=i-1;treeedges[l][1]=j-1;}
    }       
    //identify number of neighbors for each node
    long ineighbors[100001]={0},in[100001]={0},nneighbors[100000]={0};
    for (long l=0;l<n-1;l++){
        nneighbors[treeedges[l][0]]++;nneighbors[treeedges[l][1]]++;
    }
    //for (long l=0;l<n;l++){printf("%ld ",nneighbors[l]); printf("\n");}
    //use counting array to sort neighbors    
    for (long l=0;l<n+1;l++){
        ineighbors[l+1]=ineighbors[l]+nneighbors[l];
        in[l+1]=ineighbors[l+1];
    }
    //for (long l=0;l<n+1;l++){printf("%ld ",ineighbors[l]);}printf("\n");
    long neighbortotal=ineighbors[n];
    long allneighbors[neighbortotal];
    for (long l=0;l<n-1;l++){
        allneighbors[in[treeedges[l][0]]++]=treeedges[l][1];
        allneighbors[in[treeedges[l][1]]++]=treeedges[l][0];
    }    
    //for(long l=0;l<neighbortotal;l++){printf("%ld ",allneighbors[l]);}printf("\n");
    
    //fill queue with leaves
    long queue[100000], left=0,right=0;
    for (long i=0;i<n;i++){
        if(nneighbors[i]==1) queue[right++]=i;
    }
    //for (long i=left;i<right;i++){printf("%ld ",queue[i]);} printf("\n");
  
    //process queue: 
    long root;
    while(left<right){
        //for (long i=0;i<n+1;i++){printf("%ld ",ineighbors[i]);} printf("\n");
        //for (long i=left;i<right;i++){printf("%ld ",queue[i]);} printf("\n");
        long thisv=queue[left++];
        long neighbor=-1;        
        
        if(nneighbors[thisv]>0){        
            neighbor=allneighbors[ineighbors[thisv]++];
            //remove duplicate edge in other direction
            //printf("removing %ld %ld\n",neighbor, thisv);             
            long ptr=ineighbors[neighbor];
            while(allneighbors[ptr]!=thisv) ptr++;
            if(ptr>ineighbors[neighbor]){
                long swap=allneighbors[ineighbors[neighbor]];
                allneighbors[ineighbors[neighbor]]=allneighbors[ptr];
                allneighbors[ptr]=swap;
            }
            ineighbors[neighbor]++;
            nneighbors[thisv]--; //remove edge from thisv
            nneighbors[neighbor]--; 
            vvalue[neighbor]+=vvalue[thisv];  //add value of thisv
            if(nneighbors[neighbor]==1) queue[right++]=neighbor; //add to queue if now a leaf
        }
        else{
            //found root as last node in this scheme
            root=thisv;
        }
    }    
    //for (long i=0;i<n;i++){printf("%ld ",nneighbors[i]);} printf("\n");
    //for(long i=0;i<n;i++){printf("%lld ",vvalue[i]);}printf("\n");
    long long totalcost=vvalue[root];
    //now, for each v have computed accumulated value of subtree rooted at v
    long long mintreediff=totalcost;
    for (long l=0;l<n-1;l++){
        long i=treeedges[l][0], j=treeedges[l][1];
        long long cost1=(vvalue[i]<vvalue[j])?vvalue[i]:vvalue[j];
        long long cost2=totalcost-cost1;
        long long treediff=abs(cost2-cost1);
        //printf("edge %ld %ld cost %lld\n",i,j,treediff);
        if(treediff<mintreediff) mintreediff=treediff;
    }
    printf("%lld",mintreediff);   
    return 0;
}

#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;


class node {
    public:
    int v;
    int no;
    multimap<int,node*> e;
    bool visit;
    int n;
    node(int n,int no);
};
node::node (int n,int nn){
    v=n;
    no=nn;
    visit=false;
}
long mind=999999999999;
int dfs(node *n,int tt){
    int s=0,x=0,lmin;
    multimap<int,node*> newe;
    n->visit=true;
    for(auto i:n->e){
        if(!i.second->visit){
            x = dfs(i.second,tt);
            lmin=abs(2*x-tt);
            if(lmin<mind){
                mind=lmin;
                //cout<<n->no<<" "<<mind<<endl;
            }
            s+=x;
            newe.insert(make_pair(x,i.second));
        }
    }
    n->e.clear();
    n->e=newe;
    return s+n->v;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int n,x,y,ss=0;
    cin>>n;
    node *a[n+1];
    for(int i=1;i<=n;i++){
        cin>>x;
        a[i] = new node(x,i);
        ss+=x;
    }
    for(int i=1;i<=n-1;i++){
        cin>>x>>y;
        a[x]->e.insert(make_pair(9999999999,a[y]));
        a[y]->e.insert(make_pair(9999999999,a[x]));
    }
    int s = dfs(a[1],ss);
    cout<<mind;
    return 0;
}

using System;
using System.Collections.Generic;
using System.IO;
class Node {
    public int Value;
    public int SumValue;
    public int ReachedTimes;
    public List<Node> Sons = new List<Node>();
}
class Solution {
    static int ReadInt() {
        while (true) {
         if (__line == null) __line = System.Console.ReadLine().Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
         if (__line.Length > __index) {
             __index++;
             return Int32.Parse(__line[__index-1]);
         } else { __line = null; __index = 0; continue; }
        }
    }
    static string[] __line;
    static int __index;
    static int leastdiff = int.MaxValue;
    static int everything;
    static int[] values;
    static List<Node> tree = new List<Node>();
    static void dfs(int type, Node node, Node parent) {
        int sum = 0;
        
        if (type == 2 && parent != null) {
            // What is my parent?
            int parentis = everything - node.SumValue;
            // What am I?
            int iam = node.SumValue;
            
            int diff = Math.Abs( parentis - iam );
            if (diff < leastdiff) {
                leastdiff = diff;
            }
            
        }
        
        foreach(Node son in node.Sons) {
            if (son != parent) {
                dfs(type, son, node);
                if (type == 1) {
                    sum += son.SumValue;
                }
            }
        }
        if (type == 1) {
            node.SumValue = sum + node.Value;
        }
    }
    static void Main(String[] args) {
        int n = ReadInt();
        values = new int[n];
        for (int i =0;i<n;i++) {
            values[i] = ReadInt();
            Node node = new Node();
            everything += values[i];
            node.Value = values[i];
            tree.Add(node);
        }
        // Read links
        for (int i =0;i<n-1;i++) {
            int from = ReadInt();
            int to = ReadInt();
            tree[from-1].Sons.Add(tree[to-1]);
            tree[to-1].Sons.Add(tree[from-1]);
        }
        // DFS 1
        dfs(1, tree[0], null);
        // DFS 2
        dfs(2, tree[0], null);
        
        Console.WriteLine(leastdiff);
    }
}

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'cutTheTree' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY data
     *  2. 2D_INTEGER_ARRAY edges
     */

    public static int cutTheTree(List<Integer> data, List<List<Integer>> edges) {

        // Approach:
        //
        // (1) Build a graph with nodes containing value and sum subTree
        //     => Root will contain whole tree sum.
        //       1:12
        //      / | \
        //     /  |  \
        //  1:1  1:9  1:1
        //      / | \
        //     /  |  \
        //  1:1  6:6  1:1
        //
        // (2) Iterate over the graph and figure out min dif using child sums.

        final int n = data.size();

        List<Integer>[] children = new List[n];
        for (int i = 0; i < n; i++) children[i] = new ArrayList<>();
        int i1, i2;
        for (List<Integer> edge : edges) {
            i1 = edge.get(0) - 1;
            i2 = edge.get(1) - 1;
            children[i1].add(i2);
            children[i2].add(i1);
        }
        boolean[] visited = new boolean[n];
        visited[0] = true;
        Node root = new Node(0, data.get(0));
        root.subTreeSum = addChildren(root, children, data, visited);

        return minDif(root, root.subTreeSum, Integer.MAX_VALUE);
    }

    static int addChildren(
        Node node,
        List<Integer>[] children,
        List<Integer> data,
        boolean[] visited
    ) {
        int subTreeSum = 0;
        for (int i : children[node.id]) {
            if (visited[i]) continue;
            visited[i] = true;
            Node child = new Node(i, data.get(i));
            child.subTreeSum = addChildren(child, children, data, visited);
            if (node.children == null) node.children = new ArrayList<>();
            node.children.add(child);
            subTreeSum += child.subTreeSum;
        }
        return node.val + subTreeSum;
    }

    static int minDif(Node node, int treeSum, int curMinDif) {
        int dif = treeSum - 2*node.subTreeSum;
        if (dif == 0) return 0; // edge case
        if (dif < 0) dif *= -1;
        if (curMinDif > dif) curMinDif = dif;
        if (node.children != null)
            for (Node child : node.children)
                curMinDif = minDif(child, treeSum, curMinDif);
        return curMinDif;
    }

    static final class Node {
        int id;
        int val;
        int subTreeSum;
        List<Node> children;

        Node(int id, int val) {
            this.id = id;
            this.val = val;
            this.subTreeSum = 0;
        }
    }   
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> data = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        List<List<Integer>> edges = new ArrayList<>();

        IntStream.range(0, n - 1).forEach(i -> {
            try {
                edges.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                        .map(Integer::parseInt)
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        int result = Result.cutTheTree(data, edges);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

function processData(input) {
    var lines = input.split('\n');
    var n = lines[0];
    var nodes = lines[1].split(' ').map(function(x){
        return {
            edges:[],
            data:parseFloat(x),
            sum:parseFloat(x),
            children:0,
            contributed:0
        };
    });
    for (var i = 2; i < lines.length; ++i) {
        var ab = lines[i].split(' ').map(function(x){return parseInt(x)-1;})
        nodes[ab[0]].edges.push(ab[1]);
        nodes[ab[1]].edges.push(ab[0]);
    }
    
    var queue = [0];
    while (queue.length) {
        var ptr = queue[queue.length-1];
        var node = nodes[ptr];
        
        if (!node.visited) {
            for (var i = 0; i < node.edges.length; ++i) {
                var childPtr = node.edges[i];
                var child = nodes[childPtr];
                if (child.visited)
                    continue;
                node.children++;
                child.parent = ptr;
                queue.push(childPtr);
            }
        }
        node.visited = true;

        if (node.contributed == node.children) {
            queue.pop();
            if (node.hasOwnProperty('parent')) {
                var parent = nodes[node.parent];
                parent.sum += node.sum;
                parent.contributed++;
            }
        }
    }
    
    var best = nodes[0].sum;
    for (var i = 0; i < nodes.length; ++i) {
        best = Math.min(best, Math.abs(nodes[0].sum-2*nodes[i].sum));
    }
    console.log(best);
  
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

class Tree(object):
	
	def __init__(self, value):
		self.value = value
		self.adj = []
		self.parentTotal = 0
		self.total = value
		self.parent = -1
		self.auxIndex = 0
		self.sumMax = -1 
	
def calculateTotalI(nodes, root):
	stack = [int]*len(nodes)
	stack[0] = root
	stackIndex = 0
	
	while stackIndex >= 0:
		currentIndex = stack[stackIndex]
		current = nodes[currentIndex]
		if current.auxIndex >= len(current.adj):
			stackIndex -= 1
			nodes[current.parent].total += current.total
		else:
			while current.auxIndex < len(current.adj):
				if current.adj[current.auxIndex] != current.parent:
					stackIndex += 1
					stack[stackIndex] = current.adj[current.auxIndex] 
					current.auxIndex += 1
					nodes[stack[stackIndex]].parent = currentIndex
					break
				else:
					current.auxIndex += 1

def calculateParentTotalI(nodes, root):
	queue = [int]*len(nodes)
	queue[0] = root
	qIndex = 0
	while qIndex >= 0:
		current = nodes[queue[qIndex]]
		qIndex -= 1
		for n in current.adj:
			if n != current.parent:
				nodes[n].parentTotal = current.parentTotal + current.total - nodes[n].total
				qIndex += 1
				queue[qIndex] = n
	
def minCutI(nodes, root, min):
	queue = [int]*len(nodes)
	queue[0] = root
	qIndex = 0
	currentMin = min
	while qIndex >= 0:
		current = nodes[queue[qIndex]]
		qIndex -= 1
		for n in current.adj:
			if n != current.parent:
				qIndex += 1
				queue[qIndex] = n
				total1 = nodes[n].parentTotal
				total2 = nodes[n].total
				total = abs(total1 - total2)
				if total < currentMin:
					currentMin = total
				
	return currentMin

if __name__=="__main__":
	N = int(input())
	values = input().split()
	values = [ int(x) for x in values ]
	nodes = [None]*N
	root = -1
	sumMax = sum(values)
	for x in range(N):
		nodes[x] = Tree(values[x])
		nodes[x].min = sumMax

	for z in range(N-1):
		i, j = input().split()
		i, j = int(i)-1, int(j)-1
		
		if root == -1:
			root = i

		nodes[i].adj.append(j)
		nodes[j].adj.append(i)

	calculateTotalI(nodes,root)
	calculateParentTotalI(nodes,root)
	print(minCutI(nodes, root, sum(values)))