Elearning CodePath – CTP Online Judge

Truy vấn trên cây (Subtree, Point and Path)

TREE_QUERY

🟢 Easy #Tree #Segment 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ó giá trị là 0. Có q truy vấn thuộc một trong ba dạng sau:
- Dạng 1 (1 u x): Tăng giá trị của tất cả các đỉnh trong cây con gốc u lên x đơn vị.
- Dạng 2 (2 u x): Tăng giá trị của riêng đỉnh u lên x đơn vị.
- Dạng 3 (3 u v): Tính tổng giá trị các đỉnh trên đường đi đơn từ đỉnh u đến đỉnh v.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file TREE_QUERY.INP:
- Dòng đầu tiên gồm hai số nguyên n và q (1 <= n, q <= 2 * 10^5).
- n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v mô tả một cạnh của cây.
- q dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng nêu trên.

### 📤 Định dạng Đầu ra
Với mỗi truy vấn loại 3, in ra một số nguyên là tổng tìm được trên một dòng.

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

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

✅ Đã AC: 0 / 0 submissions