Submission I would like to explain the logic used to solve problem E (which I didn't manage to complete during the contest and submitted shortly after).

For this, it will be useful to know what Catalan numbers are, as well as how to derive their formula. You can read about Catalan numbers in detail, for example, on wiki: click, Catalan numbers can be defined in different ways, but we will define the number $$$C_n$$$ as the number of balanced bracket sequences of length $$$2n.$$$ We are interested in the following relatively well-known and elegant method to find this number.

Let’s consider a coordinate grid where we need to walk from $$$(0,0)$$$ to $$$(n,n)$$$. We can only move to the right or up. A step to the right corresponds to an opening bracket, and a step up — to a closing one. Thus, there is a one-to-one correspondence between a valid bracket sequence of length $$$2n$$$ and a path from $$$(0,0)$$$ to $$$(n,n)$$$ that does not cross the diagonal $$$y=x$$$; since a point above this diagonal would mean that in the current prefix, there are more closing brackets than opening ones. How can we find the number of such paths?

The total number of paths is $$$\binom{2n}{n}.$$$ From this number, we subtract the number of invalid paths. Invalid paths are those that cross $$$y=x$$$, or, equivalently, have at least one common point with the line $$$y=x+1.$$$ Take the first (with the smallest $$$x$$$) common point $$$(a, a+1)$$$ and reflect the segment of the path from $$$(0,0)$$$ to $$$(a, a+1)$$$ across the line $$$y=x+1.$$$ We obtain a path from $$$(-1,1)$$$ to $$$(n,n)$$$. This is a one-to-one correspondence. Indeed, any path starting at $$$(0,0)$$$ that has common points with $$$y=x+1$$$ can be reflected up to the first such point. At the same time, any path from $$$(-1,1)$$$ to $$$(n,n)$$$ must have common points with с $$$y=x+1$$$, since the start and end points of the path are on opposite sides of the line, which means we can also reflect the segment of the path up to the first such point. The number of such invalid paths is $$$\binom{2n}{n+1}.$$$ (or, equivalently $$$\binom{2n}{n-1}.$$$) Therefore, the number of valid paths is $$$C_n = \binom{2n}{n} - \binom{2n}{n+1}.$$$ This is Catalan number. More on the figure below.

If there were no trump suit in the problem, the winning distribution of cards between the players would satisfy the condition that all cards of the same suit are distributed in the order of a balanced bracket sequence, with $$$m/2$$$ cards for each player. However, the presence of a trump suit requires us to make two modifications to the above formula.

First, suit 1 must still satisfy the prefix condition of a balanced bracket sequence, but it does not have to be completed. Any path from $$$(0,0)$$$ в $$$(a, m-a), a \ge m-a$$$, that does not intersect $$$y=x$$$, satisfies the condition. The number of such paths is $$$\binom{m}{a} - \binom{m}{a+1}$$$. This distribution of suits will leave us with $$$2a - m$$$ trump cards that we can use for other suits. This is the basis of our DP. Let $$$dp_i[ta]$$$ be the number of ways to arrange the first $$$i$$$ suits in a winning way, leaving $$$ta$$$ trump cards available for later use. Then $$$dp_1[2a - m] = \binom{m}{a} - \binom{m}{a+1} \forall a \ge m/2.$$$

Second, if we use $$$k$$$ (even number) trump cards for suit $$$i \ne 1$$$, it means that player 1 plays $$$(m - k)/2$$$ cards of suit $$$i$$$ and player 2 plays $$$(m+k)/2$$$ cards. The cards must satisfy the condition of a "not too imbalanced" bracket sequence, meaning that on any prefix, the number of closing brackets should not exceed the number of opening brackets by more than $$$k.$$$

Combining these ideas, we find that the result is the number of paths from $$$(0,0)$$$ to $$$(\frac{m - k}{2}, \frac{m + k}{2})$$$, that do not intersect $$$y = x + k$$$. Invalid paths are reflected in a similar way as before, but across the line $$$y = x + k + 1$$$, to the paths that start at $$$( -(k+1), (k+1))$$$. Thus the number of valid path is $$$f(m,k) = \binom{m}{(m - k)/2} - \binom{m}{(m - k)/2 + k + 1}$$$.

The DP transition itself is easy: $$$\forall ta \le m, \forall k \le ta, dp_i[ta - k] += f(m,k)*dp_{i-1}[ta].$$$ It's enough to consider only even $$$ta$$$ и $$$k$$$. The final answer is $$$dp_n[0].$$$ The complexity is $$$O(m^2n).$$$

120700765
This is similar to the solution suggested by OleschY, although uses single dfs per node.
Using the linearity of expectation, the answer to this problem is a sum of probability of inversion for each pair $$$i \lt j$$$.

For every node $$$i$$$, we can find this probability for each node $$$j \gt i$$$, as following:
Root tree at node $$$i$$$. Start DFS in $$$i$$$ that will calculate two following values for each node $$$v$$$: the size of subtree rooted at $$$v$$$, $$$sz(v)$$$ and the parent of $$$v$$$, $$$p(v)$$$.
Now consider every node $$$j \gt i$$$, as shown in the figure. What is the probability that it will be marked before marking node $$$i$$$? There are three cases:
1) With probability $$$sz(j)/n$$$ we will start in the subtree of $$$j$$$. Conditional on that, we will mark node $$$j$$$ earlier than node $$$i$$$ with probability 1.
2) We start in $$$i$$$ or any subtree of a child of $$$i$$$ rather than the one containing node $$$j$$$. In that case we reach node $$$i$$$ before $$$j$$$. So probability if inversion conditional on that is zero.
3) We start somewhere on the path from $$$i$$$ to $$$j$$$, or on any subtree branching from that path. Let's look on the picture:
With probability $$$1/n$$$ we start at some node $$$p_k$$$. If we start at node $$$p_1$$$ we need one move down the path from $$$i$$$ to $$$j$$$ to get the inversion, or two moves up the path, to reach $$$i$$$ and to prevent inversion. Generally, if there are $$$m$$$ nodes on the path from $$$i$$$ to $$$j$$$ (excluding $$$i$$$ and $$$j$$$), $$$p_1$$$ — parent of $$$j$$$ ... $$$p_m$$$ -- child of $$$i$$$, then the probability of inversion conditional on starting in node $$$p_k$$$ is equal to the probability of throwing $$$k$$$ heads earlier than throwing $$$m+1-k$$$ tails. That is a known probability question, and the answer to it can be calculating recursively, as with equal probability we reduce the problem to that with one less head to get to the goal, or with one less tail to get to the goal. Let $$$x$$$ be the desired number of heads, and $$$z$$$ — the total length of path, $$$m+1$$$. Then

With border conditions $$$P(z,0) = 1$$$, $$$P(z,z) = 0$$$.
At last, what happens if we start in some subtree branching from the node on the path, as shown in the cloud on the picture? It turns out, that in that case, no matter when and whether we cover this whole branch, at some point we will be at node $$$p_2$$$ before moving along the $$$i-j$$$ path. So the aformentioned probabilities can be just weighted with the size of the tree branching from the node $$$p_2$$$ (shown in the cloud), which is calculated as $$$sz(p_2) - sz(p_1)$$$, or generally $$$sz(p_k) - sz(p_{k-1})$$$, where $$$p_0$$$ is node $$$j$$$ itself.
We can reconstruct the path easily, as we stored each parent while running DFS, and precompute $$$P(z,x)$$$ for all the values less than n. The total complexity is $$$O(n^3)$$$, as for every pair $$$i,j$$$ we processed the path from $$$i$$$ to $$$j$$$ which has length up to $$$n$$$.