I really loved Power Tree! Here is my solution for it:

##
Click to view

First of all the size of PT(X) is 2^X. It can be shown pretty easily based on the recursive formula. As a result, if N isn’t a power of 2 then the answer is -1. Otherwise we can always remove edges to get PT(log(N)).

Notice, that PT(X) can be constructed by taking two PT(X-1)-s and connecting their roots. The direction of the edge between the two roots obviously don’t matter. Because we have a tournament (complete directed graph) we will always find such an edge between the two roots.

We can construct PT(log(N)) using the following algorithm. Let’s have a vector V containing roots of power trees. Initially we will have N PT(0)-s, so V = \{1,2,\ldots,N\}. In each step pair up the elemnts of V and merge the two power trees. We can do this by finding the direction of the edge between the two roots. This will make V contain power trees of degree one higher than previously and the size of V will be halved. Since N is a power of 2 we can make these steps until we are left with only 1 element in V the root of a PT(log(N)). We can store the used edges during the merging, and print out the remaining \frac{N(N-1)}{2}-(N-1) edges as the answer.

Here is my code.