Update each product with all the parent categories of each last level category of a category tree. You can use this gist, when you have products that only have the last child category of a category tree assigned. Tested on Magento 1.7.0.2.

Magento_updateProductCategories.php

<?php

require_once 'app/Mage.php';

Mage::app();

$pids   = array();

$products = Mage::getModel('catalog/product')
    			->getCollection();

foreach ($products as $product) {
	
	if($product->getId() != 0) {
		
		$cpaths = array();
		
		foreach($product->getCategoryIds() as $k=>$v){
			
			#Get Parent Categories From Each Category
			$categories = Mage::getModel('catalog/category')
							->getCollection()
							->addAttributeToSelect('*')
							->addFieldToFilter('entity_id', $v);			
							
			foreach($categories as $category){
				
				#Get Category Path
				$cpath = $category->getPath();
				$path = explode('/', $cpath);											
				
				#Remove Root Category
				array_shift($path);
				
				#Push elements to @cpaths
				foreach($path as $p){
					array_push($cpaths,$p);
				}							

			}

		}
		
		#Remove Duplicate Category IDs
		$cpaths = array_map("unserialize", array_unique(array_map("serialize", $cpaths)));
		
		#Save Category IDs to Product
		$product->setCategoryIds($cpaths);
		$product->save();
		
		echo "PRODUCT ID ".$product->getId()." :: DONE :: ADDED :: ".count($cpaths)." CATEGORIES<br/>";
	}

}

?>