Get Categories of Products on Special Offer

As you said you got product collection let assume product collection is $collection.

    $cat = array();
    foreach ($collection as $col) {
        foreach ($col->getCategoryIds() as $catId) {
            //check if category id exist.
            if(!in_array($catId, $cat))
            {
               //push to $cat
                array_push($cat,$catId);
            }
        }
    }

$cat variable store category id of products.

Now load category collection by category ids.

    $categoryCollection = Mage::getModel('catalog/category')->getCollection()->addFieldToFilter('entity_id',array('in' => $cat));
    foreach ($categoryCollection as $catCol) {
        echo $catCol->getId();
    }

This is long way to do this.

or you can set flag as category attribute while special price set.

So you already have the products inside the $collection object.
You can do this.

$categoryIds = array();
foreach ($collection as $product) {
   $categoryIds = array_merge($categoryIds, $product->getCategoryIds());
}
$categoryIds = array_unique($categoryIds);

Now you have the category ids you need.
Here is how you can get the top level categories that have ids among the ones you filtered above.

if (count($categoryIds) > 0) {
    $categories = Mage::getModel('catalog/category')->getCollection()
        //add the attributes you need to the select. * = all.
        ->addAttributeToSelect('*')
        //filter by ids you need
        ->addAttributeToFilter('entity_id', array('in' => $categoryIds))
        //get only active categories
        ->addAttributeToFilter('is_active', 1)
        //get only top level categories: 2 means top level (1 is root catalog and 0 is root of all roots)
        ->addAttributeToFilter('level', 2)
        //sort by position if needed
        ->addAttributeToSort('position', 'ASC');
}

Now you can just loop through the categories collection and do what you need with your category. You don't need to call load anymore for each one.