给定一棵树和一个起点，1号节点为终点，随机选其中K条边变成指向终点的单向边，在树上随机游走，求到达终点的期望步数。

不考虑选单向边，设 $f_x$ 为从 $x$ 走到其父亲的期望步数，则有 $f_x=\dfrac{1+\sum_v (1+f_v+f_x)}{d(x)}$，化简可得$f_x=d(x)+\sum_vf_v=2size(x)-1 $，其中 $size(x)$ 为 $x$ 的子树大小。
设出发点 $s$，其到 $1$ 的路径 $L$ 为 $s,v_k,\cdots,v_1,1$，则答案 $ans=f_s+f_{v_k}+\cdots+f_{v_1}$
考虑单向边 (v,u) 带来的影响，当该边到 $L$ 的路径上没有单项边时会对答案产生贡献，设路径长度为 $len$, $L$ 与该路径交点到 $1$ 的路径长度为 $L^\prime$,则对答案的贡献为 $$ -\dfrac{2*size(v)*\sum_{i=0}^{L^\prime-1}C_{n-1-len-i}^{K-1}}{C_{n-1}^{K-1}} $$ 预处理前缀和，时间复杂度 $O(n)$