Cho một cây gồm \(N\) đỉnh và \(N - 1\) cạnh vô hướng, các cạnh đều có độ dài bằng \(1\). Các đỉnh được đánh số từ \(1\) đến \(N\). Mỗi đỉnh \(u\) trên cây ban đầu được tô một màu cố định \(C\lbrack u\rbrack\) (được mô tả bằng một số nguyên). Bạn 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\}\)).

Yêu cầu: Với mỗi truy vấn, hãy đếm số lượng cặp đỉnh phân biệt \((u,v)\) thỏa mãn đồng thời các điều kiện sau:

1. Cả hai đỉnh \(u\) và \(v\) đều thuộc tập \(S\) (\(u \in S,v \in S\)).

2. Hai đỉnh \(u\) và \(v\) có cùng màu trên cây gốc (\(C\lbrack u\rbrack = C\lbrack v\rbrack\)).

3. Trên đường đi duy nhất nối giữa \(u\) và \(v\) trên cây gốc, không tồn tại bất kỳ đỉnh nào khác thuộc tập \(S\). (Nói cách khác, \(u\) và \(v\) phải là hai đỉnh “nhìn thấy nhau trực tiếp” trong tập \(S\), đường đi giữa chúng không bị chặn bởi một nút trọng yếu nào khác).

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 \(C\lbrack 1\rbrack,C\lbrack 2\rbrack,\ldots,C\lbrack N\rbrack\) mô tả màu của từng đỉnh (\(1 \leq C\lbrack i\rbrack \leq N\)).

• \(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 là số lượng cặp đỉnh thỏa mãn yêu cầu.

Ví dụ:

Ràng buộc

• Subtask 1 (25% số điểm): \(N,Q \leq 1000\), tổng \(\sum_{}^{}K \leq 2000\).

• Subtask 2 (35% số điểm): Tất cả các đỉnh trên cây gốc đều có cùng một màu (\(C\lbrack i\rbrack = 1\) với mọi \(1 \leq i \leq N\)) và \(\sum_{}^{}K \leq 2 \cdot 10^{5}\).

• Subtask 3 (40% 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}\), màu sắc ngẫu nhiên.