Make sure the initial "A" node has been removed from the trash then run the update/common/scripts/updateniceurls.php script with appropriate parameters
Did it for the simple case, I'm afraid that's a little bit more tricky for some other cases (eg if you rename a node A to B, it keeps the alias A and it doesn't rename A_1 to A).
Between
kernel/classes/ezcontentobjecttreenode.php (updateURLAlias) and kernel/classes/ezurlalias.php
and some SQL commands, I'm going to clean as I want it, hopefully without screwing too much my db ;)
For the record: add a --help on the updateniceurls list the options (like -s siteaccess if you don't want the default one).