{"code":"tmaxset","name":"Tìm tập độc lập cực đại trên cây — TMAXSET","description":"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\r\ntrọng số lớn nhất trong $Q$.\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa một số $T \\le 20$ là số lượng bộ test;\r\n- Mỗi test có cấu trúc như sau:\r\n\r\n- Dòng đầu chứa $2$ số $n$ và $m$ là số đỉnh và số cạnh của đồ thị;\r\n- Dòng thứ $2$ chứa $n$ số là trọng số trên mỗi đỉnh;\r\n- 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\r\nđảm bảo đồ thị đã cho là $1$ cây;\r\n- 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ố:\r\n\r\n – Số đầu tiên trong dãy $k$ chỉ số lượng của tập đỉnh truy vấn:\r\n\r\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\r\n\r\n

Output

\r\n\r\n- 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\r\nmột dòng trống.\r\n\r\n

Scoring

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 1\r\n 3 2\r\n 5 4 10\r\n 0 2\r\n 2 1\r\n 1\r\n 2 2 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 10\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n 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$ và $2$ cạnh (0 2) và (2 1). Có $1$ truy\r\n vấn chỉ xét trên $2$ đỉnh có số hiệu $1$ và $2$.","points":100.0,"partial":true,"time_limit":1.0,"memory_limit":512000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}