There are many possible magic labellings and it is possible to work systematically and to use simple algebraic arguments to find them all (see the hint to get started). Also it is possible to find a magic vertex labelling and a magic edge labelling for 20. Jo sent us her labelled trees:
I thought about what conditions I had, and used them to narrow down the number of possibilities, then just tried some things out, and they worked! I expect that there are lots more possibilities, but I don't know. Anyway, here are my trees.