CF802L - Click Here
Description
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.
Input
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.
Output
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$.)
Solutions
第一次听到这题是在PKUWC2018。D2T3是一道概率与期望的题，朴素做法是构造出线性方程组然后高斯消元，时间复杂度是$O(n^3)$的。后来在评讲时听说了对于树上的与度数有关的DP，能够通过某种方法做到$O(n)$高斯消元。
回到本题。考虑朴素做法，设$f(i)$表示到达点$i$的期望路径。
则易得转移方程$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$的儿子集合。
注意到这个方程只存在儿子节点与父亲节点，因此可以将$f(i)$转换成$f(i)=a_if(fa_i)+b_i$的形式。
考虑边界条件。对于叶子节点$x$，显然$a_x=b_x=0$；对于根节点$root$，由于不存在父亲节点，$f(root)=b_{root}$。
边界条件都是已知的，可以自底向上推导出所有点的$a_i,b_i$，这样就计算出了所有点的$f$值。
时间复杂度$O(n)$
CODE
CODE - Click Here