We consider dynamic programming. Let $$$\mathrm{dp}_{i,j,0/1}$$$ represent the expected number of steps when currently at node $$$i$$$ with $$$j$$$ coins and about to take an even/odd step. To simplify the formulation: - Define $$$\mathrm{sc}_i := \text{number of children of } i, p_i := \text{parent of } i$$$. - The initial condition is $$$\mathrm{dp}_{1,j,0/1} = 1$$$.

Odd steps are straightforward:

From the problem description:

The "not to pay" case involves both the parent and children, making it more complex. However, observe that:

This implies that for the "not to pay" case:

Reorganizing:

Thus:

考虑 dp，设 $$$\mathrm{dp}_{i,j,0/1}$$$ 表示目前走到节点 $$$i$$$，有 $$$j$$$ 块钱，将要走第偶数 / 奇数步的答案。为了方便表述，定义

初始情况显然是

奇数步也很好递推：

对于偶数步，根据题目可得：

不付钱的情况与父亲和儿子都有关，比较难搞。但是不难注意到

也就是说，对于不付钱的情况：

所以