I think you have to do some hand work so I would suggest to chose one database export links and categories and cat links to a flatfile, open it with e.g. Excel, add the amount of the last link-id to links and cat links and do the same with categories. I think you should be fine after manually changing the root categories back to 0. maybe someone else has a better idea.

good luck and always backup ;-)