CF802L Send the Fool Further! (hard)

Heidi 被你的估算吓坏了，她觉得她的朋友们不会联合起来让她陷入债务之中，这种想法不现实。她认为，实际上，每个人只会随机选择一个朋友将 Heidi 送过去（这种随机假设意味着，她现在可以无数次地拜访同一个朋友……）。此外，如果某人只和 Heidi 有一个共同的朋友（也就是说，这个人在社交树上是一个叶子节点），那么此人不会把 Heidi 再送回来（这样 Heidi 的旅行最终会结束）。 Heidi 还觉得你假设她能在一天之内完成所有旅行也不现实。因此，她现在假设每次在两个朋友之间旅行，都需要购买一张新的车票。她想知道：预计在这些旅行中她应该花多少钱？ 值得一提的是，Heidi 已知 Jenny 至少有两个朋友。

第一行包含朋友数 $n$（$3 \leq n \leq 10^5$）。接下来的 $n-1$ 行中，每行包含三个用空格分隔的整数 $u$，$v$ 和 $c$（$0 \leq u,v \leq n-1$，$1 \leq c \leq 10^4$），表示 $u$ 和 $v$ 是朋友，且在 $u$ 和 $v$ 之间旅行的费用为 $c$（每次都需要支付！）。 输入保证社交网络的结构是一棵树。

假设旅行的期望总费用为最简分数 $a/b$（即 $a$ 和 $b$ 互质）。Heidi 这个奇怪的奶牛让你输出 $a \times b^{-1} \bmod (10^9+7)$。（输出为一个介于 $0$ 和 $10^9+6$ 之间的整数。）

在第一个样例中，Heidi 以 $1/2$ 的概率会从 $0$ 前往 $1$，以 $1/2$ 的概率前往 $2$。第一种情况费用为 $10$，第二种为 $20$。到达 $1$ 或 $2$ 后就停止旅行，因为 $1$ 和 $2$ 是树的叶子节点。因此她需要支付的期望费用是 $10 \times 1/2 + 20 \times 1/2 = 15$。 在第三个样例中，期望费用为 $81/5$，你应输出 $400000019$。 在旅行过程中，Heidi 学到了一些关于社交网络结构的有趣事实。她告诉你：那个神秘的行列式，即使你对此感到好奇，在合理解法下也不会引起奇怪的错误……我们提过 Heidi 是个怪奶牛了吗？ 由 ChatGPT 5 翻译