#!/usr/bin/perl

use strict;

my %parent=();	# Store name of parent for a node
my %weight=();	# Store weight for a node
my %children=();

while( my $x = <> ) {
	chomp( $x );
	if( $x =~ /^([a-z]+) \((\d+)\)$/ ) {
		my $n=$1;
		my $w=$2;
		$weight{$n}=$w;	# Store node weight
	} elsif( $x =~ /^([a-z]+) \((\d+)\) -> (.*)$/ ) {
		my $n=$1;
		my $w=$2;
		my $children=$3;
		$weight{$n}=$w;	# Store node weight
		$children=~s/\s+//g;
		foreach my $c ( split /,/, $children ) {
			# Store name of parent for this node
			$parent{$c}=$n;
			push( @{$children{$n}}, $c );
		}
	} else {
		print "UNHANDLED: [$x]\n";
		exit;
	}
}

# 7a - find the base node, it's the one with no parent

my $base=undef;
foreach my $n ( keys %weight ) {
	if( !exists( $parent{$n}) ) {
		if( ! defined( $base ) ) {
			print "BASE: $n\n";
			$base=$n;
		} else {
			print "ARGH: Tree has at least two unconnected nodes: $base and $n\n";
			exit;
		}
	}
}

findit( $base );

exit;

sub findit {
	my ( $node ) = @_;
	if( ! haschildren($node) ) {
		print "ARGH: $node has no children\n";
		exit;
	}
	foreach my $loop ( children( $node ) ) {
		if( haschildren( $loop ) ) {
			if( defined( oddweightchild( $loop ) ) ) {
				print "$loop has odd weight, recursing\n";
				findit( $loop );
				return;
			}
		}
	}
	# Children don't contain any unbalanced subtrees
	my $owc = oddweightchild( $node );
	if( !defined( $owc ) ) {
		print "ARGH: No odd weight child for $node\n";
		exit;
	}
	# We know the odd weight, find the other common weight
	my $rightweight=undef;
	foreach my $n ( children( $node ) ) {
		my $twn = totweight( $n );
		if( $twn != totweight($owc) ) {
			if( !defined( $rightweight ) ) {
				$rightweight=$twn;
			}
			if( $twn != $rightweight ) {
				print "ARGH: Differing other weights at $node n=$twn rw=$rightweight\n";
				exit;
			}
		}
	}
	if( !defined( $rightweight ) ) {
		print "Can't find right weight at $node\n";
		exit;
	}
	print "$owc has children with the same weights, so it must be $owc itself\n";
	print "$owc weighs $weight{$owc}\n";
	print "if $owc was ".($weight{$owc}-(totweight($owc)-$rightweight))." then it would balance.\n";
}

sub oddweightchild {
	my ( $node ) = @_;
	my @cw=();
	my %wct=();
	if( ! haschildren( $node ) ) {
		print "ARGH: $node has no children\n";
		exit;
	}
	foreach my $n ( children( $node ) ) {
		my $tcw=totweight($n);
		push( @cw, $tcw );
		$wct{ $tcw }++;
	}
	my $oddweight=undef;
	foreach my $w ( keys %wct ) {
		if( $wct{$w} == 1 ) {
			if( !defined( $oddweight ) ) {
				$oddweight=$w;
			} else {
				print "HMM: Already got an odd weight of $oddweight instead of $w at $node\n";
				exit;
			}
		}
	}
	my $oddnode=undef;
	foreach my $n ( children( $node ) ) {
		if( totweight($n) == $oddweight ) {
			if( !defined( $oddnode ) ) {
				$oddnode=$n;
			} else {
				print "HMM: Already got an oddnode of $oddnode instead of $n at $node\n";
				exit;
			}	
		}
	}
	return( $oddnode );
}

sub totweight {
	my ( $node ) = @_;
	my $sum=0;
	foreach my $n ( children( $node ) ) {
		$sum+=totweight($n);
	}
	$sum+=$weight{$node};
	return( $sum );
}

sub haschildren {
	my ( $node ) = @_;
	return(1) if( scalar( children( $node ) ) > 0 );
	return(0);
}

sub children {
	my ( $parent ) = @_;
	if( !defined( $children{$parent} ) ) {
		return( () );
	}
	return( @{$children{$parent}} );
	# Or use the below if we aren't storing children...
	my @ret=();
	foreach my $c ( keys %parent ) {
		push( @ret, $c ) if( $parent{$c} eq $parent );
	}
	return( @ret );
}