Do both.

You MUST keep your chlorine levels up or you WILL have problems.

Lowering the alkalinity takes time and patience. In any case, that's probably not the cause of the stains.

Try to avoid UCC products. They do work, but they tend to be 'black magic' like, in that there's always a price to pay for using them. That's one reason why I came up with, and why we emphasize, the BBB method: -- using as few things as possible in your pool greatly increases your chance for success.