Subtask 1

Let ~E_u~ be the minimum expected time to reach node ~1~ from node ~u~, where ~E_1=0~.

Observe that if the tree is rooted at ~1~, when in an uncrowded node, you must move towards the parent as you must pass through the parent on the route to ~1~; that is, for an uncrowded node ~u~ we have ~E_u=w_u+E_{f_u}~, where ~f_u~ is the father of ~u~ and ~w_u~ is the weight of the edge between ~u~ and ~f_u~.

On the other hand, in a crowded node you cannot control where the next step is, so ~E_u=\frac{1}{k_u}\left[(w_u+E_{f_u})+\sum\limits_{ch}(w_{ch}+E_{ch})\right]~ where ~ch~ sums over all children of ~u~, and ~k_u~ is the number of neighbors of ~u~.

We claim that for all nodes ~E_u~ we can express it as ~a_u+b_uE_{f_u}~ for rational ~a_u~ and ~b_u~. It is trivial to prove this inductively; for a leaf or uncrowded node we have ~a_u=w_u~ and ~b_u=1~, and for a crowded node we have

$$\displaystyle \begin{align*} E_u &= \frac{1}{k_u}\left[(w_u+E_{f_u})+\sum_{ch}(w_{ch}+E_{ch})\right] \\ E_u &= \frac{1}{k_u}\left[(w_u+E_{f_u})+\sum_{ch}(w_{ch}+a_{ch}+b_{ch}E_u)\right] \\ \left(1-\frac{1}{k_u}\sum_{ch}b_{ch}\right)E_u &= \frac{w_u+\sum_{ch}(w_{ch}+a_{ch})}{k_u}+\frac{1}{k_u}E_{f_u} \end{align*}$$

For the first subtask, we can directly use this to calculate ~a_u~, ~b_u~, and ~E_u~ for every node.

Time Complexity: ~\mathcal{O}(n + q)~

Subtask 2

We claim that for every non-root node, ~b_u=1~. We also prove this inductively; for a leaf and uncrowded node this holds, and for a crowded node there are ~k_u-1~ children, each of which have ~b_{ch}=1~ by the inductive hypothesis; hence the recurrence that we established above becomes

$$\displaystyle \begin{align*} \frac{1}{k_u}E_u &= \frac{w_u+\sum_{ch}(w_{ch}+a_{ch})}{k_u}+\frac{1}{k_u}E_{f_u} \\ E_u &= w_u+\sum_{ch}(w_{ch}+a_{ch})+E_{f_u} \end{align*}$$

In other words, ~E_u~ is the sum of ~a_u~ over all ancestors of ~u~, where

$$\displaystyle a_u=\begin{cases}w_u&\text{uncrowded}\\w_u+\sum\limits_{ch}(w_{ch}+a_{ch})&\text{crowded}\end{cases}$$

Consider maintaining ~a_u~ for each node with HLD. As we modify the value of ~a_u~ for a node, we have to update all ancestors of ~u~ in the current connected component formed by crowded nodes; if we can maintain this connected component with a DSU this becomes a classic path-add path-sum query problem.

Time Complexity: ~\mathcal{O}(n\log n+q\log^2n)~ using HLD, or ~\mathcal{O}((n+q)\log n)~ with LCT.