Replacing the sky

[Riftvalley]

Hi,
Is there a procedure to replace the sky in an image. I need to brighten a number of images shot on an overcast day. I have tried introducing a new sky and it works very well, by using the pen tool and a bit of patience and a touch of feathering.

Where I come unstuck is where a tree is silhouetted against the sky, I wonder if anyone has a way to make a tree look ok - I cannot imagine trying to trace round all the leaves!!! I did try cutting out the leaf parts and using light and dark cotones for sky and leaves respectively and this is reasonable, but not perfect.

I attach the sort of thing I need to put a better sky behind (the example I have selected has some purple fringing that is not representative).

Kind regards

Martin