My usual technique in your situation is to clean up any burned PCB residue. If the existing trace is missing, enlarge the hole in the PCB where the trace / pad used to connect to the relay pin. Tin that pin on the relay (heck - tin them all). Remove any excess solder after tinning - you want to see the square corners of the relay contact pins.
Install the relay and solder the coil terminals. Scrape the solder mask away from both traces that connect to the relay contacts.
Take some bare solid (not stranded) 22 AWG wire and wrap at least one full turn around each of the relay's contact terminals. One and a half turns, actually. Wrap as tightly around the pin as possible. You want to wind up with two pieces of bare wire hanging from the relay pin. Obviously, the direction that the bare wire tails is pointing is towards the trace. The wire should not "wiggle" if you try to move it - you want the square corners of the relay pin digging into the copper conductor.
The reason for enlarging the hole in the PCB where the missing trace/pad was is to ensure that you can get a full wrap and a half around the pin. Push the first turn into the PCB if you have to.
Now lay those two wire tails onto the PCB trace. Cut to length, then solder the tails to the trace. Solder the wrap of wire to the relay pin. Use a good quality soldering iron that has plenty of heat capacity.
I use Metcal soldering stations, so I never have to worry about getting enough heat to the terminal to ensure a perfect solder joint. But Weller or Hako (or any of the Asian clones) might not have the ability to deliver enough heat to guarantee a perfect solder joint without risking damaging the relay. All you can do is try it.
A very short piece of #22 wire can easily handle 20 or 25 Amps so long as it is a very short length and the ends of the wire are attached to something that can take the heat away. The relay pin is one of those heatsinks, the PCB trace is the other. You have two pieces of wire, so double that current rating.
I have done exactly this kind of repair many times before, usually in older Industrial equipment where replacement boards are not available. This technique has proven to be extremely reliable.
For those who might question using such thin wire to handle those currents: think about the total cross-section of copper of 2- #22 wire conductors compared to the total cross-section of the PCB trace width. The wire has significantly more copper content than the PCB trace.