First, let’s find the probability that the score is not \(0\).

Since real numbers are difficult to understand, let’s consider a discrete problem. For an integer \(M\), consider the problem of writing values in \([-(N-1) \times M, M]\) on each vertex and finding the probability of satisfying \(0 \leq x_i \leq M\).

After writing values on each vertex, suppose we contract each connected component of vertices with the same \(x_i\) into a single group.

Now, fix \(K\) groups \(C_1, \cdots, C_K\) and their \(x_i\) values \(y_1, \cdots, y_K\). Here, we assume all \(y_i\) are distinct.

The number of ways to write values that achieve this state is:

• \(\prod_{1 \leq i \leq K} (y_i+1)^{|C_i|-1}\)

This can be understood as follows:

First, consider the group \(C_i\) where \(y_i\) is maximum. Extract the subtree corresponding to this group, root it at an appropriate vertex, and call it \(T_i\). For each edge, the sum of values in the subtree below should be in \([0, y_i]\), and within that range, we can choose freely. We can make this choice independently for all edges. Finally, considering that the sum of values for the entire subtree is \(y_i\), the number of ways to write values achieving \(y_i\) in this subtree is \((y_i+1)^{|C_i|-1}\).

We can think similarly when \(y_i\) is not maximum. For some vertex \(v\) in this group, suppose the value \(y_j\) of an adjacent group \(C_j\) is greater than \(y_i\). Here, when a subtree containing \(v\) achieves \(x_v\), it must contain all of \(C_j\). Then, \(y_j\) can be considered as an offset for the value of vertex \(v\). By exactly the same argument as before, the number of ways to write values so that \(T_i\) has value \(y_i\) is \((y_i+1)^{|C_i|-1}\).

Based on this consideration, returning the problem to \([0,1]\) real numbers, it becomes:

• Try all ways to decompose the tree into several subtrees.
• For each subtree with \(c\) vertices, apply a weight of \(\int_{0}^{1} x^{c-1} = 1/c\)
• Sum the products of weights for all methods.

We haven’t accounted for the score here, but this is just a matter of changing the weight to \(\int_{0}^{1} x^c \times x^{c-1} = 1/(2c)\).

We just need to solve this problem, which can be done in \(O(N^2)\) time using typical tree DP.

Solution Example (C++)