题意
做法
等价成每个点父亲比其小
考虑新加入点的在(1)下面的子树大小
有(sumlimits_{i=2}^n {n-ichoose m-1}(m-1)!(n-m-1)!m)为恒等式
令(f_i)为子树大小为(i)获胜的概率
有(1-f_i=sumlimits_{j=1}^{i-1}f_j imes(1-f_{i-j})),即(f_i=1-sumlimits_{j=1}^{i-1}f_j imes (1-f_{i-j}))
分治ntt即可
题意
今天状态好差啊...
等价成每个点父亲比其小
考虑新加入点的在(1)下面的子树大小
有(sumlimits_{i=2}^n {n-ichoose m-1}(m-1)!(n-m-1)!m)为恒等式
令(f_i)为子树大小为(i)获胜的概率
有(1-f_i=sumlimits_{j=1}^{i-1}f_j imes(1-f_{i-j})),即(f_i=1-sumlimits_{j=1}^{i-1}f_j imes (1-f_{i-j}))
分治ntt即可
今天状态好差啊...