Mạng lưới bưu cục quốc gia
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Truy vấn trên cây
Cho một cây gồm $n$ đỉnh được đánh số từ $1$ đến $n$, gốc của cây là đỉnh $1$.
Có $m$ truy vấn. Mỗi truy vấn cho một tập gồm $k$ đỉnh $v_1, v_2, \dots, v_k$. Nhiệm vụ của bạn là kiểm tra xem có tồn tại một đường đi đơn bắt đầu từ gốc (đỉnh $1$) sao cho mọi đỉnh $v_i$ trong truy vấn đều nằm trên đường đi này hoặc kề với một đỉnh trên đường đi này (khoảng cách đến đường đi $\le 1$).
Dữ liệu vào
- Dòng 1: Hai số nguyên $n$ và $m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 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 của cây ($1 \le u, v \le n$).
- $m$ dòng tiếp theo: Mỗi dòng mô tả một truy vấn, bắt đầu bằng số nguyên $k_i$ ($1 \le k_i \le n$), theo sau là $k_i$ số nguyên $v_1, v_2, \dots, v_{k_i}$.
- Đảm bảo tổng $k_i$ trên tất cả truy vấn không vượt quá $2 \cdot 10^5$.
Dữ liệu ra
Với mỗi truy vấn, in ra YES nếu tồn tại đường đi thỏa mãn, ngược lại in ra NO.
Community Discussion