| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P151SUMJ - ROUND 1J - Cây may mắn |
Số may mắn là số mà chỉ gồm các chữ số 4 và 7. Ví dụ các số 4, 7, 744 là các số may mắn còn 43, 247 thì không.
Cho một cây có n đỉnh. Ngoài ra, mỗi cạnh trên cây đều có trọng số là một số nguyên dương. Một cạnh gọi là may mắn nếu trọng số cạnh đó là một số may mắn.
Nhiệm vụ của bạn bây giờ là xem có bao nhiêu bộ 3 đỉnh (i, j, k) thỏa mãn. Đường đi từ i đến j cũng như đường đi từ i đến k đều chứa một cạnh may mắn. Biết rằng bộ (i, j, k) khác bộ (i, k, j) cũng như khác bộ (p, q, t) với p khác i.
Input
Dòng đầu tiên chứa số nguyên n(1 <= n <= 10^5) là số đỉnh của cây.
n – 1 dòng tiếp theo, dòng thứ i chứa 3 số u[i], v[i], w[i] (1 <= u[i], v[i] <=n, 1 <= w[i] <= 10^9) thể hiện có cạnh nối đỉnh u[i] với cạnh v[i] và cạnh có trọng số w[i].
Output
Một dòng duy nhất chứa kết quả của bài toán.
Example
Test 1:
Input:
4
1 2 4
3 1 2
1 4 7
Output:
16
Test 2:
Input:
4
1 2 4
1 3 47
1 4 7447
Output:
24
Giải thích:
Test 1: Có 16 cặp sau: (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)
| Được gửi lên bởi: | adm |
| Ngày: | 2015-07-02 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
