Computing sharp bounds for hard clustering problems on trees