The problem asks us to allocate a permutation to the vertices of a rooted tree so that the value of a parent is smaller than that of its child.

If it were not for the condition \(P_U<P_V\), we just have to find the product of \(1/(\)size of subtree\()\) over the vertices of the tree.

The trouble is that introducing the condition \(P_U<P_V\) breaks the tree structure of restrictions.

Let \(W\) be the parent of \(V\). We will detach \(V\) from \(W\), along with its descendants, and attach it to \(U\) as its child. Let us try to count the sought permutations in this tree. The condition \(P_U<P_V\) is always satisfied, while the condition \(P_W<P_V\) is taken out.

Now, let us consider the problem in this tree with the additional restriction \(P_V<P_W\) and add the answer multiplied by \((-1)\) to the final result.

This new problem has the same structure as the original problem. Thus, we can again detach \(W\) from its parent and make it a child of \(V\), and repeat this to keep reducing the problem to another.

If \(P_x<P_y\) denotes the additional restriction, the distance between \(LCA(x,y)\) and \(y\) decreases by \(1\) at a time, so this reduction ends after \(O(N)\) iterations.

Now, we just have to solve the problem with the tree. It is possible to dutifully find the number of sought permutations, but you can ignore the common terms in the numerator and denominator of the final probability, which will simplify the implementation. Eventually, we need to find the product of the sizes of the subtrees rooted at the vertices along the \(x-y\) path, which can be done in \(O(N)\).

Therefore, the problem can be solved in \(O(N^2)\) in total.

The time limit is somewhat loose, so a solution that finds mod inverse \(O(N^2)\) times should also pass (without too much constant factor).

Sample solution

Quiz: There exists an \(O(N \log^2N)\) solution.