First, we'll calculate the expected beauty of a path that starts at the root. We can calculate it with a standard dynamic ~down[v] = val[v] + \sum_{c \in child[v]} prob[v][c] \times down[c]~, where ~val[v]~ is the beauty of park ~v~ and ~prob[v][c]~ is the probability that Vito goes from park ~v~ to park ~u~ (from now on we're assuming he starts in the root). It only remains to calculate ~prob[v][c]~.

In the third subtask the graph is a binary tree so we know that every vertex can have ~0~, ~1~ or ~2~ children. If ~v~ has one child, the probability that the edge is directed downwards is ~50\%~ and in that case Vito takes that road. If it has two children we have four cases: both edges directed downwards, only left edge downwards, only right edge downwards and neither edge directed downwards. Each case has a probability of ~25\%~, in second (third) case Vito continues his path towards left (right) child, in fourth case his journey ends, and in the first case he randomly chooses towards which child he'll go with probabilities ~50/50~. Summing up probabilities that Vito goes towards left child over all cases we get ~37.5\%~. We get the same value for probability he goes towards the right child and we can now solve ~50\%~ of third subtask.

Observation. Probability that from vertex ~v~ Vito goes to his child ~c~ is equal for every child of ~v~.

It follows from the symmetry, and we can convince ourselves by analysing cases for arbitrary pair of children similar to the former analysis.

Since the probability that Vito ends his path in vertex ~v~ with ~k~ children is ~2^{-k}~ (all edges directed upwards), it follows that probability that he takes a path from ~v~ to its child ~c~ is equal to ~prob[v][c] = pr(k) = \frac{1-2^{-k}}{k}~. Applying dynamic programming to all starting vertices we get a solution with time complexity ~\mathcal{O}(n^2)~ for complete second subtask.

For final solution we have to apply rerooting. For that we need expected value of a path given that from the starting vertex we go upwards. In case where parent of current vertex is not the root we can calculate that value by adding expected beauty of path upwards of parent and subtractic expected beauty of path starting at parent and going to current vertex: ~up[v] = val[v] + down[p] + up[p] - prob[p][v] \times down[v]~. And if the parent is the root then we subtract the expected beauty of path towards current vertex and normalize probability due to the change of number of children: ~up[v] = val[v] + \frac{pr(k-1)}{pr(k)} (down[p] - prob[p][v] \times (down[v] + val[p]))~, for ~k~ the number of children of root ~p = 1~.

Now we can calculate the expected beauty of path starting at arbitrary vertex with ~down[v]~ and ~up[v]~ in ~\mathcal{O}(1)~. Total time complexity is ~\mathcal{O}(n)~.

For complete solution of the third subtask it was enough to calculate the probability for ~k \le 3~ and apply rerooting.

Alternatively, we can apply general rerooting algorithm in time complexity ~\mathcal{O}(n \log n)~.