翻译
查看原帖
翻译
444201
Dawalishi_Ball楼主2024/7/21 20:55

题意翻译

一个有向加权森林是无环有向加权图,其中每个顶点至多有一条边。有向加权森林中,顶点 vv 的根是一个没有出边的顶点,并且可以通过沿着加权有向森林的边从顶点 vv 到达。现将顶点 vv 的根记为root(v)root(v)。顶点v的深度是从顶点 vv 到其根的路径的权重之和。现将顶点 vv 的深度表示为depth(v)depth(v)。

构建加权定向森林的过程如下:最初,森林不包含顶点。顶点按顺序逐个添加。总体而言,有 nn 个执行的加法操作。

第 i(i>0) i(i>0)个 加法运算由一组数字 (kk,v1v1,x1x1,v2v2, x2x2, ... vkvk,xkxk) 描述,意味着我们应该将顶点 ii 和 边 kk 添加到图中

从顶点 root(v1v1) 到顶点 i 的边,权重为depth(v1v1) + x1 ;从顶点 root(v2v2) 到顶点ii的边,权重为 depth(v2v2) + x2x2 ,以此类推。如果是k=0k=0,那么图中只增加了顶点 ii ,没有增加任何边。

现给定添加顶点的运算,请计算森林所有边的权重之和。由于数据可能很大,请将输出的数据模 10000000071000000007 (109+710^9 + 7)。

输入格式

第一行包含一个整数 n(1 ≤ n ≤ 105)n (1 ≤ n ≤ 105)

接下来的 nn 行表示进行的操作,第 ii 行包含添加第 ii 个顶点的操作说明

每行的第一个数字为整数k(0 ≤ k ≤ i − 1)k (0 ≤ k ≤ i - 1)之后是 2k2k 空格分隔的整数: v1, x1, v2, x2, ..., vk, xk.(1 ≤ vj ≤ i − 1, ∣xj∣ ≤ 109)v1, x1, v2, x2, ... , vk, xk. (1 ≤ vj ≤ i - 1, |xj| ≤ 109) .

这些运算按照应用于图形的顺序进行。保证所有操作的总和kk不超过105105,同时保证添加顶点的操作不会导致循环和多条边。

输出格式

一行一个整数表示图中所有边的权重之和,模数为1000000007(109 + 7)1000000007 (10^9 + 7)。

2024/7/21 20:55
加载中...