Cho một vương quốc hình cây gồm \(N\) đỉnh và \(N - 1\) cạnh vô hướng. Các đỉnh được đánh số từ \(1\) đến \(N\), mỗi đỉnh \(u\) có một tài nguyên quốc gia trị giá \(A\lbrack u\rbrack\) (đơn vị: vàng). Hoàng gia cần xử lý \(Q\) truy vấn độc lập. Mỗi truy vấn cung cấp một tập hợp \(S\) gồm \(K\) đỉnh ngẫu nhiên (\(S = \left\{ x_{1},x_{2},\ldots,x_{K} \right\}\)) đại diện cho các thành phố đang tổ chức lễ hội.

Yêu cầu: Với mỗi truy vấn, hãy chọn ra một tập con các thành phố \(P\) nằm trong tập \(S\) (\(P \subseteq S\)) sao cho:

1. Tổng giá trị tài nguyên của các thành phố được chọn là lớn nhất có thể (\(\sum_{v \in P}^{}A\lbrack v\rbrack \rightarrow \text{Max}\)).

2. Điều kiện bảo an: Không tồn tại bất kỳ hai thành phố nào trong tập chọn \(P\) mà đường đi đơn giữa chúng trên cây gốc chỉ đi qua các thành phố thuộc tập \(S\). (Nói cách khác, hai thành phố được chọn trong \(P\) không được “nhìn thấy nhau trực tiếp” thông qua các thành phố lễ hội khác, đường đi giữa chúng bắt buộc phải bị ngắt quãng bởi ít nhất một thành phố bình thường không nằm trong tập \(S\)).

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \leq N,Q \leq 2 \cdot 10^{5}\)).

• Dòng thứ hai chứa \(N\) số nguyên \(A\lbrack 1\rbrack,A\lbrack 2\rbrack,\ldots,A\lbrack N\rbrack\) mô tả tài nguyên của từng đỉnh (\(1 \leq A\lbrack i\rbrack \leq 10^{9}\)).

• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) mô tả một cạnh của cây.

• Tiếp theo là \(Q\) nhóm dòng, mỗi nhóm mô tả một truy vấn:

  • Dòng đầu chứa số nguyên \(K\) – số lượng thành phố trong tập \(S\) (\(1 \leq K \leq N\)).

  • Dòng tiếp theo chứa \(K\) số nguyên phân biệt \(x_{1},x_{2},\ldots,x_{K}\) (\(1 \leq x_{i} \leq N\)).

Kết quả:

• Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng là tổng tài nguyên lớn nhất có thể thu được từ tập \(P\) thỏa mãn điều kiện bảo an.

Ví dụ:

Ràng buộc:

• Subtask 1 (15% số điểm): \(N,Q \leq 20\), \(K \leq N\) (Duyệt trâu quay lui mọi tập con).

• Subtask 2 (25% số điểm): \(N,Q \leq 2000\), và cấu trúc cây gốc có dạng một ngôi sao (Nút \(1\) nối với tất cả các nút còn lại).

• Subtask 3 (30% số điểm): Bản thân tập \(S\) luôn đảm bảo không chứa bất kỳ cặp đỉnh nào là cha - con trực tiếp của nhau trên cây gốc và \(\sum_{}^{}K \leq 2 \cdot 10^{5}\).

• Subtask 4 (30% số điểm): \(N,Q \leq 2 \cdot 10^{5}\), tổng số lượng đỉnh trong tất cả các truy vấn thỏa mãn \(\sum_{}^{}K \leq 2 \cdot 10^{5}\), cấu trúc cây và tập \(S\) ngẫu nhiên.