ARC086C Smuggling Marbles

题意 ： 给出一棵 个点的树，编号 ，其中 为根。

每个点上有 或 个石子，重复进行如下操作直至整棵树没有石子：

• 把 上面的石子从树上拿走放入口袋。

• 把每个点上的石子移到其父亲上。

• 对于每个点，若其石子数 ，则移除该点所有石子（不放入口袋）。

求对于所有 种放置石子的方案，最终口袋中石子数的和为多少。答案对 取模。

，时限 。

---

先考虑若给定石子放置方式如何求出口袋中的石子数。

不难发现，只有同深度的石子可能相遇，且对于每个深度最多只有可能收到一枚石子。

于是，可以对每层的节点分别考虑。

记 为 的深度， 为 子树内节点数， 为 子树内深度为 的点合并到 后，使得 为 的概率（方案数与总方案数之比）。

（若直接维护方案数，则需要更复杂的乘法标记）

边界：。

记 的直接儿子为 ，转移：

最终 的和乘以 即为答案。

可以使用长链剖分维护，复杂度 。