There is a very easy way to do this in Vegas. On the track above your trees/sky footage place a blue gradient that goes from medium to darker blue from top to bottom. Then set the composite mode for the gradient track to darken. This will cause all of the lighter sky color to be replaced with the blue gradient. If you have any other light colors in your footage they may also be replaced so you will have to mask that out, but for most footage this is easy to do.