They actually reference the root certificate in their removal instructions:

"Uninstalling Superfish Visual Discovery

    Go to Control Panel > Uninstall a Program

    Select Visual Discovery > Uninstall

Superfish will be removed from Program Files and Program Data directories, files in user directory will stay intact for the privacy reason. Registry entry and root certificate will remain as well. The Superfish service will stop working as soon as it is uninstalled via above process, and following reboot."

http://forums.lenovo.com/t5/Lenovo-P-Y-and-Z-series/Removal-...