← 返回题目列表

Codeforces · 109/C

C. 幸运树

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

Petya 喜欢幸运数字。我们都知道,幸运数字是十进制表示中仅包含幸运数字4和7的正整数。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

有一天,Petya 遇到了一棵有 n 个顶点的树。此外,这棵树是加权的,即。 e.树的每条边都有权重(正整数)。如果一条边的权重是一个幸运数字,那么它就是幸运的。请注意,具有 n 个顶点的树是恰好具有 n - 1 条边的无向连通图。

Petya 想知道从 i 到 j 的路上以及从 i 到 k 的路上必须至少有一个幸运边(所有三个顶点都是成对不同的),存在多少个顶点三元组 (i, j, k)。三元组中数字的顺序很重要,即三元组 (1, 2, 3) 不等于三元组 (2, 1, 3),也不等于三元组 (1, 3, 2)。

找出存在多少个这样的顶点三元组。

输入

第一行包含单个整数 n (1 ≤ n ≤ 105) — 树顶点的数量。接下来的 n - 1 行每行包含三个整数: ui vi wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109) — 由边和边的权重连接的一对顶点。

输出

在单行上打印单个数字 - 答案。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位数字。建议使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

4
1 2 4
3 1 2
1 4 7

输出 #1

16

输入 #2

4
1 2 4
1 3 47
1 4 7447

输出 #2

24

注意

第一个样本中的 16 个顶点三元组为: (1, 2, 4), (1, 4, 2), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 2, 4)、(3、4、2)、(4、1、2)、(4、1、3)、(4、2、1)、(4、2、3)、(4、3、1)、(4、3、2)。

在第二个样本中,应计算所有三元组:4·3·2 = 24。