Elearning CodePath – CTP Online Judge

Cập nhật cây con (Online Queries)

SUBTREE_UPDATE

🟢 Easy #Graph #Fenwick Tree

### 📝 Bài toán
Cho một cây gồm n đỉnh, đỉnh 1 là gốc. Ban đầu, mỗi đỉnh được gán giá trị 0. Có q truy vấn thuộc một trong hai dạng:
- Dạng 1 (1 u v): Tăng tất cả các đỉnh trong cây con gốc u lên v đơn vị.
- Dạng 2 (2 u): Tìm và in ra giá trị hiện tại trên đỉnh u.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file SUBTREE_UPDATE.INP:
- Dòng đầu tiên gồm hai số nguyên n và q (1 <= n, q <= 10^5).
- n - 1 dòng tiếp theo, mỗi dòng gồm 2 số nguyên u, v thể hiện có cạnh nối giữa u và v.
- q dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng nêu trên (v có thể là số âm).

### 📤 Định dạng Đầu ra
Với mỗi truy vấn loại 2, in ra giá trị trên đỉnh u tại thời điểm đó trên một dòng.

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 10 6 | 0 |
| 1 2 | 5 |
| 2 3 | 5 |
| 2 4 | -5 |
| 2 5 | |
| 2 6 | |
| 4 7 | |
| 2 8 | |
| 1 9 | |
| 9 10 | |
| 2 6 | |
| 1 2 5 | |
| 2 5 | |
| 2 6 | |
| 1 1 -5 | |
| 2 1 | |

### 🏷 Subtasks
- Subtask 1 (30%): n, q <= 2000.
- Subtask 2 (70%): n, q <= 10^5.

✅ Đã AC: 6 / 12 submissions