题目链接：P5129 不可思议的迷宫

题面

题目描述

给定一棵基环树，等概率在基环树上选取一个起点，再等概率选取终点（起点和终点可以重合），确定起点和终点后，如果会等概率选取起点到终点的一条简单路径，即不重复经过任何一条边。

求路径长度的期望，对 \(19260817\) 取模。

输入格式

第一行一个整数，表示基环树点数 \(n\) 。

接下来 \(n\) 行，每行 \(3\) 个整数 \(u,v,w\) ，表示基环树的一条边连接 \(u\) 和 \(v\) ，长度是 \(w\) 。

输出格式

一行一个整数，表示期望在模 \(19260817\) 意义下的值。

数据规模

\(1\le n\le300000\)

题解

这道题难度不大，但是坑点很多，下面我们一一清点（拉清单）。

首先，最不坑的坑点，\(i\to j\) 和 \(j\to i\) 分开计算，\(i\to i\) 只算一次。

然后，只要路径上的节点与环有交集，路径就可以从环的两侧走，这一点在样例里有部分体现。

最坑的点，若起点或终点在环上，则可以在从起点出发之前（到达终点之后）绕环一圈，你的路径中只要有一个点在环上，路径就可以从环上绕一圈，比如下面这张图中 \(1\to5\) 的路径有\(\color{red}{红色}\)和\(\color{blue}{蓝色}\)标出来的两条：