Mạng lưới bưu cục quốc gia

Buổi 20 — Cây khung nhỏ nhất Graphs Trees
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions

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.

Draft saved