Tô Màu Cây

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một cây có $N$ nút (gốc ở nút $1$ ). Có $Q$ thao tác:

Thao tác 1: 1 x c — Tô màu $c$ cho toàn bộ cây con gốc $x$ (gồm $x$ và tất cả hậu duệ của $x$ ). Mỗi nút có thể mang nhiều màu khác nhau từ các lần tô khác nhau.
Thao tác 2: 2 x — Đếm tổng số cặp (nút $v$ , màu $c$ ) mà nút $v$ thuộc cây con gốc $x$ và $v$ đang mang màu $c$ .

Dòng đầu: $N$ và $Q$ ( $1 \leq N, Q \leq 10^{5}$ ).
$N - 1$ dòng tiếp theo: mỗi dòng gồm hai số $u, v$ — cạnh nối $u$ và $v$ .
Q dòng tiếp theo: mỗi dòng là một thao tác (dạng 1 x c hoặc 2 x).
- $1 \leq x \leq N$ , $1 \leq c \leq 10^{5}$ .

Với mỗi thao tác loại 2, in kết quả trên một dòng.

Input	Output
5 18 1 2 1 3 3 4 3 5 1 4 1 2 1 2 2 2 3 2 4 2 5 1 5 1 2 1 2 2 2 3 2 4 2 5 1 1 1 2 1 2 2 2 3 2 4 2 5	1 0 1 1 0 2 0 2 1 1 5 1 3 1 1

Cây trong ví dụ có cấu trúc: nút 1 nối với 2 và 3; nút 3 nối với 4 và 5.

Sau 1 4 1: cây con gốc 4 (chỉ nút 4) được tô màu 1. Cây con gốc 1 có 1 cặp (nút 4, màu 1).

Sau 1 5 1: cây con gốc 5 (chỉ nút 5) được tô màu 1. Cây con gốc 1 có 2 cặp.

Sau 1 1 1: toàn bộ cây (cây con gốc 1) được tô màu 1. Cây con gốc 1 có 5 cặp (5 nút đều mang màu 1).

Bình luận

Không có bình luận tại thời điểm này.