Suppose the edge to be added is between u and v.
let p1=parent(u) and p2=parent(v)
Here, by parent I mean the root of the subtree in which the node lies

Now if u == p1 and v == p2 then you can simply add the edge and color them.
else if u == p1 then you can simply add the edge and colour u accordingly
else if v == p2 then you can simply add the edge and colour v accordingly
else this follows-

This is an interesting case,
if p1 == p2 then you can check if u and v have the same colour or not
else if u and v have opposite colours then simply add the edge
else now you will have to change the colour of one of the trees, either of p1 or of p2. So always choose the subtree which is smaller in size and run a dfs to change all the colours and then add the edge.