4101: CF109 - C. Lucky Tree
[Creator : ]
Description
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 withnvertexes. 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 atree 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.
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.
Input
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.
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.
Output
On the single line print the single number − the answer.
Sample 1 Input
4
1 2 4
3 1 2
1 4 7
Sample 1 Output
16
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).
Sample 2 Input
4
1 2 4
1 3 47
1 4 7447
Sample 2 Output
24
all the triples should be counted: 4·3·2 = 24.