podrias hacerlo de dos formas..... una mas sencilla que la otra claro ^^
1. al eliminar el pais, con ese mismo id del pais eliminado, haces los query para eliminar las ciudades que correspondan a ese pais con el id que tienes ..... (logico no ???)
2. en la base datos podrias crear un constraint para que se eliminen las ciudades en cascada al eliminar el pais..... algo asi:
........ espero te sirva........
suerte.