directory modification dates

I have a simple directory listing script - you can move up and down directories and it shows the files/dirs inside. Now I have to figure out a way to display the latest modification time for each directory. The problem is that filemtime() works only if the modifications are done on the first level. For example, if I add files in dir1/dir2/dir3/, then the modification time for dir1 doesn't update. My first instinct was to find the correct time recursively on each load but there are so many files and so many visitors that it clogs the server. I have a few other ideas but they seem rather ugly (like hidden files with stored info in each directory). Can you suggest any better ways to approach this problem? Marek