| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P181PROF - ROUND 1F - Sức mạnh của cây |
Cho một cây ban đầu chỉ có đỉnh gốc có chỉ số là 1. Mỗi đỉnh trong cây (gốc và các đỉnh thêm sau này) có một giá trị là vi. Sức mạnh của đỉnh S được định nghĩa:
Strength(S) = (|S|+1).(vS + ∑Strength(u)) (trong đó u là đỉnh con trực tiếp của S, |S| là số lượng đỉnh con trực tiếp của đỉnh S).
Có 2 loại truy vấn trên cây:
- Truy vấn loại 1 có dạng 1 p v, yêu cầu thêm một đỉnh mới có giá trị v làm con của đỉnh p.
- Truy vấn loại 2 có dạng 2 u, yêu cầu đưa ra sức mạnh của đỉnh u (lấy dư cho 109+7).
Input
Dòng đầu tiên chứa hai số nguyên v1, q cách nhau bởi khoảng trống (1 ≤ v1 ≤ 109, 1≤ q ≤ 200000) – giá trị của đỉnh 1 và số truy vấn.
q dòng tiếp theo, mỗi dòng mô tả một loại truy vấn:
• 1 pi vi, chỉ số của đỉnh được thêm vào là số nguyên dương nhỏ nhất chưa được sử dụng và đảm bảo rằng pi là một đỉnh đã tồn tại, 1 <= vi ≤ 109.
• 2 ui, đảm bảo đỉnh ui đã tồn tại trong cây.
Output
Với mỗi truy vấn loại 2 in ra sức mạnh của đỉnh lấy dư cho 109+7.
Example
Input:2 52 5 1 1 2 1 2 4 1 3 9 1 4 10 2 11 1 21 2 41 3 9Output: 348
Input:2 55 5 1 1 5 1 2 4 2 2 1 2 9 2 1
Output:
18
118
Giải thích test 1:
Sức mạnh của các đỉnh trên cây lần lượt là 348 – 172 – 84 – 38 - 10
| Được gửi lên bởi: | adm |
| Ngày: | 2018-03-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 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 |
