Tìm tập độc lập cực đại trên cây — TMAXSET

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 500M Input: bàn phím Output: màn hình

Cho một cây với trọng số trên mỗi đỉnh và một tập con \(Q\) các đỉnh của cây, hãy tìm tập độc lập có tổng
trọng số lớn nhất trong \(Q\).

Input

  • Dòng đầu chứa một số \(T \le 20\) là số lượng bộ test;
  • Mỗi test có cấu trúc như sau:

  • Dòng đầu chứa \(2\) số \(n\)\(m\) là số đỉnh và số cạnh của đồ thị;

  • Dòng thứ \(2\) chứa \(n\) số là trọng số trên mỗi đỉnh;
  • Từ dòng \(3\) đến dòng \(m + 2\), mỗi dòng chứa \(2\) số là các cặp đỉnh có cạnh nối giữa chúng, dữ liệu
    đảm bảo đồ thị đã cho là \(1\) cây;
  • Dòng \(m + 3\) chứa \(1\) số nguyên \(q\) là số truy vấn, sau đó mỗi dòng trong số \(q\) dòng tiếp chứa \(1\) dãy số:

    – Số đầu tiên trong dãy \(k\) chỉ số lượng của tập đỉnh truy vấn:

    \(k\) số tiếp theo chỉ số hiệu từng đỉnh trong tập (đánh số từ \(0\)) là những đỉnh xét đến trong \(n\) đỉnh ban đầu

Output

  • Mỗi truy vấn in ra \(1\) kết quả là trọng số tập độc lập lớn nhất trên \(1\) dòng. Sau mỗi một bộ test thì in ra
    một dòng trống.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(5 \le n \le 30, 1 \le q \le 100\);
  • Subtask \(2\) (\(25\%\) số điểm): \(10 \le n \le 200, 100 \le q \le 1000\);
  • Subtask \(3\) (\(25\%\) số điểm): \(150 \le n \le 200, q = 1000\).

Example

Test 1

Input
1
3 2
5 4 10
0 2
2 1
1
2 2 1
Output
10
Note

Trong ví dụ trên, có \(1\) bộ test với cây gồm \(3\) đỉnh có số hiệu là \(0,1,2\)\(2\) cạnh (0 2) và (2 1). Có \(1\) truy
vấn chỉ xét trên \(2\) đỉnh có số hiệu \(1\)\(2\).


Bình luận

Không có bình luận nào.