HackerRank Cut the Tree problem solution

In this HackerRank Cut the Tree problem solution we have given a tree and we need to determine which edge to cut so that the resulting tress have a minimal difference between them and then return that difference. remember the difference between their sums is equal to the difference between two trees. 

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)

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;
}