← 返回题目列表

Codeforces · 802/J3

J3. 让傻瓜走得更远! (难)

中文机器翻译题面 查看原题

海蒂对你的估计感到害怕,她发现她的朋友们合作让她负债累累是不现实的。她预计,实际上,每个人都会随机选择一个朋友来送海蒂去。 (然而,这种随机性假设意味着她现在可以任意次数地拜访同一个朋友......)此外,如果一个人与海蒂只有一个共同的朋友(即,如果该人在树的一片叶子中),那么该人不会将海蒂送回去(因此海蒂的旅行将在某个时刻结束)。

海蒂还发现,她可以在一天内完成所有旅行的假设是不现实的。因此,现在她假设每次她在两个朋友之间旅行时,她都需要购买一张新票。她想知道:她应该在旅行中花费多少钱?

无论如何,海蒂知道珍妮至少有两个朋友。

输入

第一行包含好友数量 n (3 ≤ n ≤ 105)。下一个 n - 1 行每行包含三个空格分隔的整数 u, v 和 c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104)意味着 u 和 v 是朋友并且往返的费用 u 和 v is c (每次都付费!)。

再次保证输入的社交网络形成一棵树。

输出

假设行程的预期成本写为不可约分数 a / b (即 a 和 b 互质)。然后海蒂这个怪牛就要求你输出 。 (输出之间的单个整数 0 和 109 + 6.)

示例

输入
复制

3
0 1 10
0 2 20

输出
复制

15

输入
复制

4
0 1 3
0 2 9
0 3 27

输出
复制

13

输入
复制

7
0 1 3
0 5 7
1 2 2
1 3 1
1 4 5
5 6 8

输出
复制

400000019

输入
复制

11
1 0 6646
2 0 8816
3 2 9375
4 2 5950
5 1 8702
6 2 2657
7 2 885
8 7 2660
9 2 5369
10 6 3798

输出
复制

153869806

输入
复制

6
0 1 8
0 2 24
1 3 40
1 4 16
4 5 8

输出
复制

39

注意

在第一个例子中,有概率 1 / 2 海蒂会去 1 来自 0,并且有概率 1 / 2 她会去 2。在第一种情况下,成本将是 10,在第二个中它将是 20。到达后 1 or 2 她会停下来,因为 1 和 2 是社交树的叶子。因此,她需要支付的预期成本是 10·1 / 2 + 20·1 / 2 = 15.

在第三个示例中,预期成本是 81 / 5。你应该输出 400000019.

在她的旅行中,海蒂了解到了关于她的社交网络结构的一个有趣的事实。她告诉你以下内容: 您可能想知道的神秘行列式是这样的,它不会在您的合理解决方案中导致奇怪的错误...... 我们有没有提到海蒂是一头奇怪的牛?