# 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)

# 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)
```

{"mode":"full","isActive":false}

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

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) {

for(int i = 0; i < ar[head].children.size(); i++) {
}
}

return sum;
}
}

class Node {
int value;
ArrayList<Integer> children;

public Node(int value) {
this.value = value;
this.children = new ArrayList<Integer>();
}

}
}```

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

## 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];
}
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;
}```

{"mode":"full","isActive":false}