plot() as usual to get the vectors. Then scatter() markers on top of that, passing in the color information as the fourth parameter, scatter(x, y, size, color)
You cannot solve this with a single plot() call or a single scatter() call by themselves. plot() does not permit different colors for the same line, and scatter() cannot join points.
There is also a possibility using patch(). There is a File Exchange contribution for colored lines that is based upon patch()