一个有向加权森林是无环有向加权图,其中每个顶点至多有一条边。有向加权森林中,顶点 v 的根是一个没有出边的顶点,并且可以通过沿着加权有向森林的边从顶点 v 到达。现将顶点 v 的根记为root(v)。顶点v的深度是从顶点 v 到其根的路径的权重之和。现将顶点 v 的深度表示为depth(v)。
构建加权定向森林的过程如下:最初,森林不包含顶点。顶点按顺序逐个添加。总体而言,有 n 个执行的加法操作。
第 i(i>0)个 加法运算由一组数字 (k,v1,x1,v2, x2, ... vk,xk) 描述,意味着我们应该将顶点 i 和 边 k 添加到图中
从顶点 root(v1) 到顶点 i 的边,权重为depth(v1) + x1 ;从顶点 root(v2) 到顶点i的边,权重为 depth(v2) + x2 ,以此类推。如果是k=0,那么图中只增加了顶点 i ,没有增加任何边。
现给定添加顶点的运算,请计算森林所有边的权重之和。由于数据可能很大,请将输出的数据模 1000000007 (109+7)。
第一行包含一个整数 n(1 ≤ n ≤ 105)
接下来的 n 行表示进行的操作,第 i 行包含添加第 i 个顶点的操作说明
每行的第一个数字为整数k(0 ≤ k ≤ i − 1)之后是 2k 空格分隔的整数: v1, x1, v2, x2, ..., vk, xk.(1 ≤ vj ≤ i − 1, ∣xj∣ ≤ 109).
这些运算按照应用于图形的顺序进行。保证所有操作的总和k不超过105,同时保证添加顶点的操作不会导致循环和多条边。
一行一个整数表示图中所有边的权重之和,模数为1000000007(109 + 7)。