Elearning CodePath – CTP Online Judge

Truy vấn cây con

SUBTREE

🟢 Easy #Graph #Data Structure

### 📝 Bài toán
Cho một cây gồm n đỉnh, đỉnh 1 là gốc. Mỗi đỉnh của cây ban đầu đều mang giá trị 0. Có q truy vấn, mỗi truy vấn có dạng (i, x) yêu cầu tăng giá trị của tất cả các đỉnh thuộc cây con gốc i thêm x đơn vị. Hãy xác định giá trị cuối cùng của mỗi đỉnh sau khi thực hiện tất cả q truy vấn.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file SUBTREE.INP:
- Dòng đầu tiên chứa hai số nguyên n và q (1 <= n, q <= 10^5).
- n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v mô tả một cạnh nối giữa đỉnh u và đỉnh v.
- q dòng cuối cùng, mỗi dòng chứa hai số nguyên i và x (1 <= i <= n, 1 <= x <= 10^9) là một truy vấn.

### 📤 Định dạng Đầu ra
Ghi ra file SUBTREE.OUT một dòng duy nhất chứa n số nguyên, số thứ k là giá trị của đỉnh k sau khi thực hiện xong các truy vấn.

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 5 2 | 1 1 3 3 3 |
| 1 2 | |
| 1 3 | |
| 3 4 | |
| 3 5 | |
| 3 2 | |
| 1 1 | |

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

✅ Đã AC: 9 / 12 submissions