Tổng Khoảng Cách Đến Các Đỉnh Đỏ
Points
35
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một cây có trọng số gồm $N$ đỉnh đánh số từ $1$ đến $N$. Ban đầu tất cả các đỉnh đều chưa được đánh dấu (màu trắng).
Hãy xử lý $Q$ truy vấn thuộc một trong hai loại sau:
1 v: Đảo trạng thái của đỉnh $v$ (nếu $v$ đang trắng thì tô đỏ; nếu $v$ đang đỏ thì tô lại thành trắng).2 v: Tính tổng khoảng cách từ đỉnh $v$ đến tất cả các đỉnh đang có màu đỏ trên cây. Nếu không có đỉnh đỏ nào, in ra0.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
- $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^6$) biểu thị cạnh nối $u$ và $v$ có trọng số $w$.
- $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn có dạng
1 vhoặc2 v($1 \le v \le N$).
Dữ liệu ra
- Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.
Ví dụ
Dữ liệu vào
4 6
1 2 2
2 3 3
2 4 4
2 1
1 3
1 4
2 1
1 3
2 1
Dữ liệu ra
0
11
6
Giới hạn
- $1 \le N, Q \le 10^5$, $1 \le w \le 10^6$.
Community Discussion