CF802L - Send the Fool Further!

CF802L - Click Here



  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 $n$ ($3 \leq n \leq 10^5$). The next $n - 1$ lines each contain three space-separated integers $u, v$ and $c$($0 \leq u, v \leq n - 1, 1 \leq c \leq 10^4$) meaning that $u$ and $v$ are friends and the cost for traveling between $u$ and $v$ is $c$ (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 $\frac{a}{b}$ (that is, $a$ and $b$ are coprime). Then Heidi, the weird cow that she is, asks you to output $a \cdot b^{-1} \, mod \, (10^9 + 7)$. (Output a single integer between $0$ and $10^9 + 6$.)






  则易得转移方程$f(i)=\frac{1}{d_i} [f(fa_i)+w(fa_i , i) + \sum_{j \in son(i)} f(j)+w(i,j)]$,其中$d_i$表示$i$的度数,$fa_i$表示 $i$的父亲节点,$son(i)$表示$i$的儿子集合。









CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang