给定一颗基环树或一颗树，从随机一个点出发，每次等概率走向之前没走过的点，知道不能走为止，求路径期望长度
数据范围对于 \(100\%\) 的数据，\(1\leq W_i\leq 100\)。
测试点编号\(n\)\(m\)备注\(1\)\(n=10\)\(m = n-1\)保证图是链状\(2\)\(n=100\)\(m = n-1\)只有节点 \(1\) 的度数大于 \(2\)\(3\)\(n=1000\)\(m = n-1\)/\(4\)\(n=10^5\)\(m = n-1\)/\(5\)\(n=10^5\)\(m = n-1\)/\(6\)\(n=10\)\(m = n\)/\(7\)\(n=100\)\(m = n\)环中节点个数 \(\leq 5\)\(8\)\(n=1000\)\(m = n\)环中节点个数 \(\leq 10\)\(9\)\(n=10^5\)\(m = n\)环中节点个数 \(\leq 15\)\(10\)\(n=10^5\)\(m = n\)环中节点个数 \(\leq 20\)解题思路对于前 50% 部分--树设 \(e[x]\) 为从 x 开始走的路径期望长度，\(d[x]\) 为从 x 开始一直向子树走的路径期望长度
\(d[x]\) 可以简单树形 dp 得到 \(d[x] = \sum_{y \in subtreee(x)}\frac {d[y]+w[x][y]}{son[x]}\)
e[x] 考虑换根 dp，维护从 x 向上走的期望长度 res，\(res=\frac{e[x]*(sons[x] + 1)-(d[y]+w[x][y])}{sons[x]} + w[x][y]\)，x 为根时要特殊讨论一下，\(e[x] = \frac{res + d[x]*sons[x]}{sons[x] + 1}\)，x 为根时 \(e[x] = d[x]\)。
带码
void dfs1(int x, int fa) {for (int i = h[x]; i; i = ne[i]) {int y = to[i]; if (y == fa) continue;dfs1(y, x); d[x] += d[y] + w[i], sons[x]++;}if (sons[x]) d[x] /= sons[x];}void dfs2(int x, int fa, double res) {if (x != 1) e[x] = (d[x] * sons[x] + res) / (sons[x] + 1);else e[x] = d[x];for (int i = h[x]; i; i = ne[i]) {int y = to[i]; if (y == fa) continue;if (x != 1) dfs2(y, x, (e[x] * (sons[x] + 1) - (d[y] + w[i])) / sons[x] + w[i]); else {if (sons[x] > 1) dfs2(y, x, (e[x] * sons[x] - (d[y] + w[i])) / (sons[x] - 1) + w[i]);else dfs2(y, x, w[i]);}}}对于剩下 50% 的数据--基环树基环树首先应该做的就是把环单独考虑，我们可以想象成将一些有根树的根串起来成一个环，先对每棵树求一遍 d[x] 数组，再求出从每个根开始走环的期望路径长度，最后再换根 dp 从根转移到其他节点即可，细节：根的 sons要+=2
带码
const int N = 200500;int h[N], ne[N