HackerRank Cut the Tree problem solution

In this HackerRank Cut the Tree problem solution, there is an undirected tree where each vertex is numbered from 1 to n, 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.

HackerRank Cut the Tree problem solution in Python.

import collections

n = int(input().strip())
d = dict((idx + 1, int(v)) for idx, v in enumerate(input().strip().split()))
tree = collections.defaultdict(list)

for i in range(n - 1):
    a, b = [int(_) for _ in input().strip().split()]
    tree[a].append(b)
    tree[b].append(a)
    
all_sum = sum(d.values())
sums = []

stack = collections.deque()
post = collections.deque()

stack.append(1)
seen = set([])

while stack:
    v = stack.pop()
    post.append(v)
    seen.add(v)
    
    # also remove link to parent
    pure_children = []
    for child in tree[v]:
        if child not in seen:
            stack.append(child)
            pure_children.append(child)
            
    tree[v] = pure_children
            
min_diff = all_sum 

while post:
    v = post.pop()
    if tree[v]:
        s = sum(d[c] for c in tree[v])
        d[v] += s
        
    diff = abs(all_sum - 2 * d[v])
    if diff < min_diff:
        min_diff = diff
        
print(min_diff)

Cut the Tree problem solution in Java.

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 scan = new Scanner(System.in);
        int numnodes = scan.nextInt();
        
        Node[] ar = new Node[numnodes];
        int[] subSumList = new int[numnodes];
        
        for(int i = 0; i < ar.length; i++) {
            ar[i] = new Node(scan.nextInt());
        }
        
        for(int i = 0; i < ar.length-1; i++) {
            int e1 = scan.nextInt()-1;
            int e2 = scan.nextInt()-1;
            ar[e1].addChild(e2);
            ar[e2].addChild(e1);
        }
        
        int minDiff = Integer.MAX_VALUE;
        int fullSum = subtreesum(ar, 0, subSumList, -1);
        
        for(int i = 1; i < subSumList.length; i++) {
            int sum = subSumList[i];
            int newDiff = Math.abs(fullSum - (2*sum));
            minDiff = Math.min(minDiff, newDiff);
        }
        
        System.out.println(minDiff);
    }
    
    public static int subtreesum(Node[] ar, int head, int[] ssl, int prev) {
        
       // System.out.println("At Node"+(head+1));
        int sum = ar[head].value;
        
        for(int i = 0; i < ar[head].children.size(); i++) {
            if(ar[head].children.get(i) != prev) {
                sum += subtreesum(ar, ar[head].children.get(i), ssl, head);
            }
        }
        
        ssl[head] = sum;
        
        return sum;
    }
}

class Node {
    int value;
    ArrayList<Integer> children;
    
    public Node(int value) {
        this.value = value;
        this.children = new ArrayList<Integer>();
    }
    
    public void addChild(int c) {
        this.children.add(c);
    }
}

Problem solution in C++.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 1000000007
#define total 500005
#define M 1000000000001
#define NIL 0
#define EPS 1e-5
#define INF (1<<28)
typedef unsigned long long int uint64;
typedef long long int int64;
/*
inline void fast(int &x) {
    register int64 c = getchar_unlocked();
    x = 0;
    int neg = 0;
    for(; ((c<48 || c>57) && c != '-'); c = getchar_unlocked());
    if(c=='-') {
        neg = 1;
        c = getchar_unlocked();
    }
    for(; c>47 && c<58 ; c = getchar_unlocked()) {
        x = (x<<1) + (x<<3) + c - 48;
    }
    if(neg)
        x = -x;}
        */
    //    vector<int64>ans,ans1;

int tem[100005];
int val[100005];
vector<int>v[100005];
bool visit[100005]={false};
int tot=0,tim=0;
void go(int nod){
	visit[nod]=true;
	tim++;
	tem[nod]=tim;
	//int tmp=val[nod];
	for(int i=0;i<v[nod].size();i++){
		if(visit[v[nod][i]]==false){
			go(v[nod][i]);
			val[nod]+=val[v[nod][i]];
		}
	}
	//tem[nod]=tim;
	//cnt[nod]=tmp;
}
int main(){
	int n,t,i;
	cin>>n;
	for(i=1;i<=n;i++){
	cin>>val[i];
	tot+=val[i];}
	int a,b;
	vector<pair<int,int> >edg;
	for(i=1;i<n;i++){
		cin>>a>>b;
		edg.pb(mp(a,b));
		v[a].pb(b);
		v[b].pb(a);
	}
	go(1);
	pair<int,int>tmp;
	//for(i=1;i<=n;i++)
	//cout<<tem[i]<<" "<<val[i]<<endl;
	int ans=5e8;
	for(i=0;i<edg.size();i++){
		tmp=edg[i];
		if(tem[tmp.first]>tem[tmp.second]){
		//	cout<<abs(tot-2*val[tmp.first])<<endl;
			ans=min(ans,abs(tot-2*val[tmp.first]));
		}
		else{
		//	cout<<abs(tot-2*val[tmp.second])<<endl;
			ans=min(ans,abs(tot-2*val[tmp.second]));
		}
	}
	cout<<ans<<endl;
	return 0;
}

Problem solution in C.

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

struct node 
{
    int val;
   struct node *next;  
};
struct element
{
   struct node *next;
   struct node *last; 
};
 
void add(int u, int v, struct element list[], int visit[])
{
    struct node *new =(struct node *)malloc(sizeof(struct node));
    new->val=v;
    new->next=NULL;
    if(visit[u]==1)
    {
       list[u].last->next=new;
       list[u].last=new;
    }
    else 
    {
       visit[u]=1;
       list[u].next=new;
       list[u].last=new;
    }
}
int top=0;
int Dfs(int u, int v, int stack[] ,struct element list[], int parent[], int data[])
{
    
    struct node *ptr=list[v].next;
    if(list[v].last->val==u && list[v].next->val==u)
    {
        top--;
        return data[v];
    }
    while(ptr->next!=NULL){
       if(ptr->val!=u){
         top++;  
         stack[top]=ptr->val;
         parent[ptr->val]=v;  
        }
         ptr=ptr->next;
    }    
    if(ptr->val!=u){
         top++;
         stack[top]=ptr->val;
         parent[ptr->val]=v; 
        }
    while(stack[top]!=v)
    {
       data[v]+=Dfs(v,stack[top],stack,list,parent,data);
    }
    top--;
    return data[v];
}

int main() {
    int n; 
    scanf("%i", &n);
     int data[n+2];
     int diff=1;
    int visit[100000]={0};
    struct element list[n+2];
    list[1].next=NULL;
    list[1].last=NULL;
    int parent[100000]={0};
    parent[1]==1;
    int stack[n+2];
    for (int data_i = 1; data_i <= n; data_i++) {
       scanf("%lld",&data[data_i]); 
    }
    int edges[n-1][2];
    for (int edges_i = 0; edges_i < n-1; edges_i++) {
       for (int edges_j = 0; edges_j < 2; edges_j++) {
      
          scanf("%i",&edges[edges_i][edges_j]);
       }
        parent[edges[edges_i][1]]=edges[edges_i][0];
        add(edges[edges_i][0],edges[edges_i][1],list,visit);
        add(edges[edges_i][1],edges[edges_i][0],list,visit);
    }
    stack[top]=1;
    int k= Dfs(1,1,stack,list,parent,data);
 
    if(parent[edges[0][0]]==edges[0][1])
    {
        diff=abs(data[1]-2*data[edges[0][0]]);
    }
    else
    {
        diff=abs(data[1]-2*data[edges[0][1]]);
    }
     int temp=diff;
    for (int i = 1; i <n-1; i++) {
       if(parent[edges[i][0]]==edges[i][1])
    {
        temp=abs(data[1]-2*data[edges[i][0]]);
    }
    else
    {
        temp=abs(data[1]-2*data[edges[i][1]]);
    }
       if(temp<diff)
       {
           diff=temp;
       }
    }
    printf("%d",diff);
    return 0;
}