Raju and his Trees
All submissions for this problem are available.
Raju loves data structures. He has a special knack for problems related to trees. One day, he stumbled upon one such problem related to nodes & edges of weighted trees. The problem asked him to find the total number of vertex triplets (i, j, k) on the way from i to j and from i to k such that there exists at least one lucky edge. A triplet (1, 2, 3) is different from (1, 3, 2) or (2, 1, 3). Also, all three nodes are pairwise distinct.
An edge is considered lucky if has only 4 or 7 as its digits. For ex- 474 and 774 are lucky while 6, 87, 49 etc. are not lucky.
Help Raju in finding the total triplets of nodes.
The first line contains the single integer n — the number of tree nodes
Next n - 1 lines contain three integers each: u,v, w — the pair of nodes connected by the edge and the edge's weight
One answer denoting the total number of triplets of nodes with one lucky edge.
- 1 ≤ n ≤ 104
- 1 ≤ u,v ≤ N
- 1 ≤ w ≤ 109
Input: 4 1 2 4 3 1 2 1 4 7 Output: 16
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.