小葱觉得糖很好吃，现在要把糖卖掉。现在小葱的\(N\)位顾客形成了一棵\(N\)个点的树，小葱可以把糖卖给所有叶子节点上的人。但是，小葱不希望卖太多的糖，所以小葱会做\(K\)次操作。每次操作小葱会等概率选一条边，将两边的顾客合并成一个新顾客，并将原来连到这两个顾客的边全部连接到这个新顾客上。（除了原来这两个顾客之间的那条边）现在问小葱在做完\(K\)次操作后，期望能卖出多少颗糖。
对于\(100\%\)的数据，\(1\leq K<N\leq10^5\)。
赛时想到正解了，但因为期望题没大做过，况且还是 T4 就没感写 QwQ
根据 \(E(X+Y) = E(X) + E(Y)\) ，我们可以知道 \(E(X) = \sum_{i=1}^{n} E(i) = \sum_{i=1}^{n} P(i) \cdot 1\) ，因此我们计算每个点成为叶子时的概率即可
概率 \(=\) 满足条件方案数 \(/\) 总方案数，因此我们考虑对每个点求他可能成为答案的方案数：
- 这个点是叶子时，只要选边时不选择和叶子相连的边删掉，剩下的随便删即可，方案数即为 \((n-2)^{\underline{K}}\)
- 这个点不是叶子时，假设他所有子树大小为 \(S_1,S_2,S_3,\cdots,S_r\) ，则显然我们可以选择一个子树不删，剩下的必须删掉，方案数即为 \(\sum_{i=1}^{r} A_{K}^{S-S_i} (S_i-1)^{\underline{K-S+S_i}}\)
最终复杂度 \(O(n)\)