Hooray for long posts!
RPG Maker can handle it quite easily. Here is a quick step-by step:
Click Show Choices.
Here you can change the up to four choices.
Using the Message command, you can create the four trees however you like. Here I have it so after you make a choice, the player repeats it, as if they are talking.
Midi files are your best bet, due to the size. Charas has a good number of midis, ranging from game-rips to original tracks. There are bound to be plenty more out on the internet.
Yes. More on that later.
There are also a good number of pre-made scripts for RPG Maker XP. Here is a good range of examples, from Custom Menu Systems to a Random Loot Script to a Personality Engine. Most require simple Copy/Paste jobs, and those that don't are usually fairly detailed in their descriptions.
Just as an example of how you would do this:
Choose Conditional Branch.
Here you can make a variety of preconditions for things to happen, from needing an item to having a party member to having a certain weapon or piece of armor equiped.
You can also "stack" conditions. Here, you need both Firewood and Flint to make a fire. Choosing "Yes turns on a switch...
Which can change the event to another page, with entirely different possibilities.
A much easier option would be to simply use the "Change Hero Class" event command. Especially since I'm not sure how you would make it so the game changed one characters level to reflect that of another.