Adding menu names to the ul menus in Drupal 7

gistfile1.php

function themename_menu_link(&$variables) {
  $element = $variables['element'];
  $sub_menu = '';

  $element['#attributes']['data-menu-parent'] = $element['#original_link']['menu_name'] . '-' . $element['#original_link']['depth'];

  if ($element['#below']) {
    $sub_menu = drupal_render($element['#below']);
  }

  $output = l($element['#title'], $element['#href'], $element['#localized_options']);
  return '<li' . drupal_attributes($element['#attributes']) . '>' . $output . $sub_menu . "</li>\n";
}

function themename_preprocess_menu_tree(&$variables) {
  $tree = new DOMDocument();
  $tree->loadHTML($variables['tree']);
  $links = $tree->getElementsByTagname('li');
  $parent = '';

  foreach ($links as $link) {
    $parent = $link->getAttribute('data-menu-parent');
  }

  $variables['menu_parent'] = $parent;
}

function themename_menu_tree(&$variables) {
  return '<ul class="menu ' . $variables['menu_parent'] . '">' . $variables['tree'] . '</ul>';
}

Thank you very much for this approach. It's pure genius. I'll take "novel" over "theme_menu_tree" any day. Forked your gist and fixed couple of bugs. 1) @ before $tree->loadHTML() will get rid of errors about HTML5 tags (are those from new DOMDocument()?) and most importantly big one b) break in foreach loop will return correct $parent value (first li, not last, since last one is deepest level in deeper nested trees).