CF195E Building Forest

定义一个有向加权森林是一个无环有向加权图，其中每个点至多只有一条出边。有向加权森林中顶点 $v$ 的根是一个没有出边且可以沿着加权有向森林的边从顶点 $v$ 到达的顶点。我们用 $\operatorname{root}(v)$ 表示顶点 $v$ 的根。 顶点 $v$ 的深度是从顶点 $v$ 到其根的路径权重之和。我们用 $\operatorname{depth}(v)$ 表示顶点 $v$ 的深度。 考虑如何构建一个有向加权森林。最初，森林中没有任何顶点，而 $n$ 个顶点将会通过 $n$ 次添加操作以 $1\sim n$ 的顺序逐步被添加到森林中。具体地，第 $i$ 次操作被描述为 $(k,v_1,x_1,v_2,x_2,\dots,v_k,x_k)$，代表点 $i$ 将在被添加入森林的同时加入 $k$ 条有向边，其中第 $j$ 条边应为从 $\operatorname{root}(v_j)$ 指向 $i$，权值为 $\operatorname{depth}(v_j)+x_j$ 的有向边。若 $k=0$，则代表只有点 $i$ 被加入森林，但并未同时添加任何边。 现在给定 $n$ 次添加顶点的操作，计算所有点加入后森林的所有边权之和，对 $(10^9+7)$ 取模。

第一行包含一个整数 $n(1\le n\le10^5)$，即要往森林中添加点的数量。 接下来的 $n$ 行将描述添加点的操作，第 $i$ 行包含第 $i$ 次添加操作的描述：第一个数字是一个整数 $k(0\le k\le i-1)$，接下来包含 $2k$ 个以空格分隔的整数：$v_1,x_1,v_2,x_2,\dots,v_k,x_k(1\le v_j\le i-1,|x_j|\le10^9)$。 这些操作按顺序给出，保证所有操作的 $\sum k\le10^5$。保证森林中没有环和重边。

一行一个整数表示图中所有边权之和，对 $(10^9+7)$ 取模。

考虑第一个样例： - 添加顶点 $1$。$k=0$，因此不添加任何边。 - 添加顶点 $2$。$k=0$，因此不添加任何边。 - 添加顶点 $3$。$k=1$，$v_1=2$，$x_1=1$。从顶点 $\operatorname{root}(2)=2$ 到顶点 $3$ 添加一条边，权值为 $\operatorname{depth}(2)+x_1=0+1=1$。 - 添加顶点 $4$。$k=2$。 - $v_1=1$，$x_1=5$：从顶点 $\operatorname{root}(1)=1$ 到顶点 $4$ 添加一条边，权值为 $\operatorname{depth}(1)+x_1=0+5=5$。 - $v_2=2$，$x_2=2$：从顶点 $\operatorname{root}(2)=3$ 到顶点 $4$ 添加一条边，权值为 $\operatorname{depth}(2)+x_2=1+2=3$ - 添加顶点 $5$。$k=1$，$v_1=1$，$x_1=2$。从顶点 $\operatorname{root}(1)=4$ 到顶点 $5$ 添加一条边，权值为 $\operatorname{depth}(1)+x_1=5+2=7$。 - 添加顶点 $6$。$k=1$，$v_1=3$，$x_1=4$。从顶点 $\operatorname{root}(3)=5$ 到顶点 $6$ 添加一条边，权值为 $\operatorname{depth}(3)+x_1=10+4=14$。 得到的图如下图所示：