By confining the structure to hashes and avoiding arrays you don't have to worry about duplicates and, by always pre-assigning an anoymous hash, you can also dispense with the bother of turning a scalar value into a hash or an array. I think this is a little simpler and clearer than muba's solution if the structure produced is what you are after.

use strict;
use warnings;

use Data::Dumper;

open my $univFH, q{<}, \ <<EOD or die qq{open: < HEREDOC: $!\n};
abc  123
abc  456
abc  789
xyz  456
EOD

my %univ;
while ( <$univFH> )
{
    my( $lev2Key, $lev1Key ) = split;
    $univ{ $lev1Key }->{ $lev2Key } = {};
}

close $univFH or die qq{close: < HEREDOC: $!\n};

print Data::Dumper->Dumpxs( [ \ %univ ], [ qw{ *univ } ] );

open my $valuesFH, q{<}, \ <<EOD or die qq{open: < HEREDOC: $!\n};
xxx ==> 456->abc
xxx ==> 789->abc
yyy ==> 456->abc
yyy ==> 456->abc
zzz ==> 123->abc
EOD

while ( <$valuesFH> )
{
    chomp;
    my( $lev3Key, $upperKeys ) = split m{\s*==>\s*};
    my( $lev1Key, $lev2Key)  = split m{->}, $upperKeys;
    $univ{ $lev1Key }->{ $lev2Key }->{ $lev3Key } = 1;
}

close $valuesFH or die qq{close: < HEREDOC: $!\n};

print Data::Dumper->Dumpxs( [ \ %univ ], [ qw{ *univ } ] );
[download]

The Data::Dumper output, first of the structure after reading the universe file and second after reading the values file and adding its data.

%univ = (
          '456' => {
                     'abc' => {},
                     'xyz' => {}
                   },
          '123' => {
                     'abc' => {}
                   },
          '789' => {
                     'abc' => {}
                   }
        );
%univ = (
          '456' => {
                     'abc' => {
                                'xxx' => 1,
                                'yyy' => 1
                              },
                     'xyz' => {}
                   },
          '123' => {
                     'abc' => {
                                'zzz' => 1
                              }
                   },
          '789' => {
                     'abc' => {
                                'xxx' => 1
                              }
                   }
        );
[download]

I hope this is helpful.