CF802L.Send the Fool Further! (hard)

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Heidi is terrified by your estimate and she found it unrealistic that her friends would collaborate to drive her into debt. She expects that, actually, each person will just pick a random friend to send Heidi to. (This randomness assumption implies, however, that she can now visit the same friend an arbitrary number of times...) Moreover, if a person only has one friend in common with Heidi (i.e., if that person is in a leaf of the tree), then that person will not send Heidi back (so that Heidi's travel will end at some point).

Heidi also found unrealistic the assumption that she can make all the travels in one day. Therefore now she assumes that every time she travels a route between two friends, she needs to buy a new ticket. She wants to know: how much should she expect to spend on the trips?

For what it's worth, Heidi knows that Jenny has at least two friends.

输入格式

The first line contains the number of friends nn ( 3<=n<=1053<=n<=10^{5} ). The next n1n-1 lines each contain three space-separated integers uu , vv and cc ( 0<=u,v<=n10<=u,v<=n-1 , 1<=c<=1041<=c<=10^{4} ) meaning that uu and vv are friends and the cost for traveling between uu and vv is cc (paid every time!).

It is again guaranteed that the social network of the input forms a tree.

输出格式

Assume that the expected cost of the trips is written as an irreducible fraction a/ba/b (that is, aa and bb are coprime). Then Heidi, the weird cow that she is, asks you to output . (Output a single integer between 00 and 109+610^{9}+6 .)

输入输出样例

  • 输入#1

    3
    0 1 10
    0 2 20
    

    输出#1

    15
    
  • 输入#2

    4
    0 1 3
    0 2 9
    0 3 27
    

    输出#2

    13
    
  • 输入#3

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

    输出#3

    400000019
    
  • 输入#4

    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
    

    输出#4

    153869806
    
  • 输入#5

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

    输出#5

    39
    

说明/提示

In the first example, with probability 1/21/2 Heidi will go to 11 from 00 , and with probability 1/21/2 she will go to 22 . In the first case the cost would be 1010 , and in the second it would be 2020 . After reaching 11 or 22 she will stop, as 11 and 22 are leaves of the social tree. Hence, the expected cost she has to pay is 101/2+201/2=1510·1/2+20·1/2=15 .

In the third example, the expected cost is 81/581/5 . You should output 400000019400000019 .

In her travels, Heidi has learned an intriguing fact about the structure of her social network. She tells you the following: The mysterious determinant that you might be wondering about is such that it does not cause strange errors in your reasonable solution... Did we mention that Heidi is a weird cow?

首页