Suppose an answer that was voted (up-voted and/or down-voted) is deleted, and undeleted after months. When it is deleted, any reputation change because that answer is removed. What happens when the answer is undeleted?
The votes still exist while the post is deleted (unless it is hard-deleted, which is rare, and in that case it can't be undeleted anyway), they just don't count for reputation. Once the post is undeleted, the votes are still still there, and they count for reputation once again.
Source: I recently discoved an answer of mine I had deleted and forgotten about, saw no real reason for it to be deleted (except maybe to get the Disciplined badge), and undeleted it. Shortly thereafter, I got an unexplained +30 (no +30 in rep log, likely the -30 from the delete just disappeared).
The reputation changes related to the votes will be restored.
Votes on answers do not decay with time (as e.g. close votes do).