← 返回题目列表

Codeforces · 833/D

D. 红黑蜘蛛网

中文机器翻译题面 查看原题

Slastyona 喜欢观察附近树林居民的生活。这次她看到一只奇怪的红黑蜘蛛坐在一张巨大的蜘蛛网的中心。

蜘蛛网是由线程连接的 n 个节点的集合,每个踏板都是红色或黑色。使用这些线程,蜘蛛可以在节点之间移动。没有线程将节点连接到自身,并且在任何两个节点之间都有唯一的线程序列连接它们。

Slastyona 决定研究蜘蛛网的一些特殊品质。她注意到每条线的粘性值为 x。

然而,Slastyona 最感兴趣的是蜘蛛网的果冻状。考虑每对节点之间的最短路径,其中红线和黑线的数量最多相差两次。对于每个这样的路径,计算路径上线程的粘性的乘积。蜘蛛网的粘性是所有路径中所有获得的值的乘积。那些仅方向不同的路径仅计算一次。

当然,这个数字可能很大,因此 Slastyona 要求您计算给定蜘蛛网的果冻度并打印模 109 + 7 的答案。

输入

第一行包含节点数 n (2 ≤ n ≤ 105)。

接下来的 n - 1 行每行包含四个整数,表示蜘蛛网的第 i 个线程:它连接的节点 ui, vi (1 ≤ ui ≤ n, 1 ≤ vi ≤ n),线程 xi 的粘稠度 (1 ≤ x ≤ 109 + 6),以及线程 ci 的颜色 ($$c_i \in \{0, 1\}$$)。红色用0表示,黑色用1表示。

输出

打印蜘蛛网的胶状度以 109 + 7 为模的单个整数。如果不存在使得红线和黑线的数量最多相差两次的路径,则打印 1。

示例

输入 #1

5
1 2 9 0
2 3 5 1
2 4 5 0
2 5 5 1

输出 #1

1265625

输入 #2

8
1 2 7 1
2 3 4 1
3 4 19 1
5 1 2 0
6 2 3 0
7 3 3 0
8 4 4 0

输出 #2

452841614

注意

在第一个示例中,有 4 对节点,其上两种颜色的线程数最多相差两倍。存在对 (1, 3),其粘性乘积等于 45,(1, 5),其粘性乘积等于 45,(3, 4),其粘性乘积等于 25,以及 (4, 5),其粘性乘积等于 25。蜘蛛网的胶冻度等于 1265625。