| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P175PROC - ROUND 5C - Tô màu |
Mật là một người rất thích cây. Một hôm, Mật được tặng một cái cây – cây là một đồ thị liên thông có N đỉnh và N-1 cạnh, cậu quyết định tô màu đỏ và đen cho các cạnh của cây. Sau khi tô màu, Mật tò mò muốn đếm xem có bao nhiêu bộ 3 đỉnh a,b,c thỏa mãn đường đi giữa 2 đỉnh bất kì luôn có ít nhất 1 cạnh có màu đỏ. Các hoán vị của (a,b,c) cũng chỉ được tính là 1 bộ 3 số thỏa mãn. Do cây quá to nên Mật không thể đếm nhanh được, các bạn hãy giúp Mật đếm xem có bao nhiêu bộ 3 đỉnh thỏa mãn nhé.
Input
Dòng đầu gồm số N là số đỉnh của cây (N<=10^5)
N-1 dòng tiếp theo, mỗi dòng chứa 2 số u,v và kí tự c
Nếu kí tự c là r nghĩa là cạnh u-v có màu đỏ.
Nếu kí tự c là b nghĩa là cạnh u-v có màu đen.
Output
Kết quả bài toán module (10^9+7)
Example
Input:
5
1 2 r
2 3 b
3 4 b
4 5 r
Output:
3
Giải thích: 3 bộ đỉnh thỏa mãn là (1,2,5), (1,3,5), (1,4,5)
| Được gửi lên bởi: | adm |
| Ngày: | 2017-03-17 |
| 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 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
