Truy vấn trên cây

Điểm: 6,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một cây có gốc gồm $n$ đỉnh được đánh số từ $1$ đến $n$ , gốc là đỉnh $1$ .

Bạn nhận được $m$ truy vấn. Truy vấn thứ $i$ cho một tập gồm $k_{i}$ đỉnh đôi một phân biệt $v_{i, 1}, v_{i, 2}, \dots, v_{i, k_{i}}$ .

Với mỗi truy vấn, hãy xác định xem có tồn tại một đỉnh $u$ sao cho mọi đỉnh trong tập đã cho hoặc thuộc đường đi từ gốc $1$ đến $u$ , hoặc có khoảng cách bằng $1$ tới một đỉnh nào đó trên đường đi này (khoảng cách giữa hai đỉnh là số cạnh trên đường đi giữa chúng).

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ — số đỉnh của cây và số truy vấn.
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_{i}$ và $v_{i}$ ( $1 \leq u_{i}, v_{i} \leq n$ , $u_{i} \neq v_{i}$ ) mô tả một cạnh của cây.
$m$ dòng tiếp theo, mỗi dòng bắt đầu bằng số nguyên $k_{i}$ rồi đến $k_{i}$ số nguyên $v_{i, 1}, v_{i, 2}, \dots, v_{i, k_{i}}$ ( $1 \leq v_{i, j} \leq n$ ).

Đảm bảo các cạnh tạo thành một cây, các đỉnh trong cùng một truy vấn đôi một phân biệt, và $\sum_{i = 1}^{m} k_{i} \leq 2 \cdot 10^{5}$ .

Dữ liệu ra

Với mỗi truy vấn, in ra "YES" nếu tồn tại đỉnh $u$ thỏa mãn yêu cầu, ngược lại in ra "NO".

Ràng buộc

$2 \leq n \leq 2 \cdot 10^{5}$
$1 \leq m \leq 2 \cdot 10^{5}$
$1 \leq k_{i} \leq n$
$\sum k_{i} \leq 2 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
10 6 1 2 1 3 1 4 2 5 2 6 3 7 7 8 7 9 9 10 4 3 8 9 10 3 2 4 6 3 2 1 5 3 4 8 2 2 6 10 3 5 4 7	YES YES YES YES NO NO	Truy vấn 1: chọn $u = 10$ , đường đi là $1 \to 3 \to 7 \to 9 \to 10$ ; các đỉnh $3, 9, 10$ thuộc đường đi, đỉnh $8$ có khoảng cách $1$ tới $7$ . Truy vấn 2: chọn $u = 2$ , các đỉnh $4, 6$ đều có khoảng cách $1$ tới đường đi $1 \to 2$ . Truy vấn 5: không tồn tại $u$ phù hợp cho tập ${6, 10}$ .
2 3 1 2 1 1 1 2 2 1 2	YES YES YES	Cây hai đỉnh; mọi truy vấn đều thỏa với $u = 2$ (hoặc $u = 1$ ).

Bình luận

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