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