You can cut the bottom loop by half (11 ⇒ 5) without making it more complex

for (grep $tree{$_}, keys %tree) {
   my @g = $_;
   push @g, $_ while $_=$tree{$_};
   print(join(':', @g), "\n");
}
[download]

And why bother with an array?

for (grep $tree{$_}, keys %tree) {
   my $g = $_;
   $g .= ":$_" while $_=$tree{$_};
   print("$g\n");
}
[download]