#!/usr/bin/perl

#  Code assumes input graph is a binary tree as stated in
#  the problem, NOT a binary *search* tree. Requres log n
#  time and space, where n is the number of nodes in the tree.
#
#  Example to compute LCA(3,6) in the tree in the diagram:
#  perl lca '8: 3 10; 3: 1 6; 6: 4 7; 10: 14; 14: 13' 3 6

use strict;
use warnings;

my($rawtree, $node1, $node2) = @ARGV;

print "LCA($node1, $node2) = ",
  LeastCommonAncestor(InvertGraph(ParseGraph($rawtree)), $node1, $node2);

sub LeastCommonAncestor {
  my ($invertedtree, $node1, $node2) = @_;

  my %parentsofnode1 = map { $_ => 1 } Descendants($invertedtree, $node1);

  foreach my $parentofnode2 (Descendants($invertedtree, $node2)) {
    if ($parentsofnode1{$parentofnode2}) {
      return $parentofnode2;
    }
  }
  die "can't happen in a tree\n";
}


sub ParseGraph {
  my ($rawgraph) = @_;
  my %graph;
  foreach (split /\s*;\s*/, $rawgraph) {
    my ($node, $successors) = /^\s*([^:\s]*):\s*(.*)/;
    $node =~ s/^\s+//;
    $graph{$node} = { map { $_ => 1 } split /\s+/, $successors };
  }
  return \%graph;
}

sub InvertGraph {
  my ($graph) = @_;
  my %invertedgraph;
  foreach my $src (keys %$graph) {
    foreach my $dst (keys %{ $graph->{$src} }) {
      $invertedgraph{$dst}{$src} = 1;
    }
  }
  return \%invertedgraph;
}

sub Descendants {
  my ($dag, $node) = @_;

  return (
    $node,
    map { Descendants($dag, $_) } Successors($dag, $node),
  );
}


sub Successors {
  my ($graph, $node) = @_;

  return keys %{ $graph->{$node} };
}