Lucky Tree

题意翻译

彼得喜欢幸运数字。这里所说的幸运数字是由 $4$ 和 $7$ 组成的正整数。比如，数字 $47$，$744$，$4$ 是幸运数字，而 $5$，$17$，$467$ 就不是。 一天，彼得遇到一棵由 $n$ 个点组成的树。另外，这棵树是带权的，即每条边有一个权值（由一个正整数表示）。如果一条边的权值是一个幸运数字，那么我们就说这条边是一条幸运边。说明一下，一棵 $n$ 个结点的树是由 $n$ 个结点和 $(n-1)$ 条边组的无环的无向图。 彼得好奇，在树中有多少个满足以下条件的三元组 $(i,j,k)$（$i,j,k$是三个不同的点）。 1. $i$ 到 $j$ 有路径，$i$ 到 $k$ 也有路径； 2. 每条路径中至少有一条幸运边。 数字的顺序是有意义的，举例说明，三元组 $(1,2,3)$，$(2,1,3)$ 和 $(1,3,2)$ 是三个不同的序列。 现在要求计算在树中存在多少个这样的三元组关系。 样例解释： 样例一中的 $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)$。 ### 输入格式 测试数据的第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$。接下来的 $(n-1)$ 行中，第 $i$ 行有三个整数 $u_i$，$v_i$，$w_i$ $(1 \leq u_i,v_i \leq n,~1\leq w_i \leq 10^9)$，分别表示有边相连的两个点和这条边的权值。 ### 输出格式 共一行，表示题目中所要计算的三元组的个数。

题目描述

Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not. One day Petya encountered a tree with $ n $ vertexes. Besides, the tree was weighted, i. e. each edge of the tree has weight (a positive integer). An edge is lucky if its weight is a lucky number. Note that a tree with $ n $ vertexes is an undirected connected graph that has exactly $ n-1 $ edges. Petya wondered how many vertex triples $ (i,j,k) $ exists that on the way from $ i $ to $ j $ , as well as on the way from $ i $ to $ k $ there must be at least one lucky edge (all three vertexes are pairwise distinct). The order of numbers in the triple matters, that is, the triple $ (1,2,3) $ is not equal to the triple $ (2,1,3) $ and is not equal to the triple $ (1,3,2) $ . Find how many such triples of vertexes exist.

输入输出格式

输入格式

The first line contains the single integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of tree vertexes. Next $ n-1 $ lines contain three integers each: $ u_{i} $ $ v_{i} $ $ w_{i} $ ( $ 1<=u_{i},v_{i}<=n,1<=w_{i}<=10^{9} $ ) — the pair of vertexes connected by the edge and the edge's weight.

输出格式

On the single line print the single number — the answer. Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is recommended to use the cin, cout streams or the %I64d specificator.

输入输出样例

输入样例 #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

说明

The $ 16 $ triples of vertexes from the first sample are: $ (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) $ . In the second sample all the triples should be counted: $ 4·3·2=24 $ .