even_tree.pl

#/usr/bin/env perl -wl
use strict;

use List::Util qw(sum);

my %graph;
<>;
while (<>) {
  my ($a, $b) = split;
  push @{$graph{$a}}, $b;
  push @{$graph{$b}}, $a;
}

my $even_subtrees;

sub traverse {
  my ($node, $parent) = @_;
  my $children_size = sum map { traverse($_, $node) } grep { $_ != $parent } @{$graph{$node}};
  $even_subtrees += $children_size % 2;
  return $children_size + 1;
}

traverse(1, 0);

print $even_subtrees - 1, "\n";