Cắt Đường Bảo Vệ Gốc · canuc80k7624

Cho một cây có trọng số cạnh gồm $n$ đỉnh, gốc là đỉnh $1$ . Phá một cạnh tốn chi phí bằng trọng số của cạnh đó.

Mỗi truy vấn cho một tập đỉnh đặc biệt, không chứa gốc. Các cạnh đã phá chỉ có hiệu lực trong truy vấn hiện tại; trước truy vấn tiếp theo, cây trở lại nguyên vẹn. Hãy tìm tổng chi phí nhỏ nhất để sau khi phá một số cạnh, gốc $1$ không còn nối được tới bất kỳ đỉnh đặc biệt nào.

Input

Dòng đầu chứa $n$ .
$n - 1$ dòng tiếp theo, mỗi dòng chứa $u$ $v$ $w$ , mô tả cạnh $u - v$ có chi phí phá là $w$ .
Dòng tiếp theo chứa số truy vấn $q$ .
Mỗi truy vấn gồm một dòng bắt đầu bằng $k$ , sau đó là $k$ đỉnh đặc biệt đôi một khác nhau.

Output

Với mỗi truy vấn, in chi phí nhỏ nhất trên một dòng.

Constraints

$2 \leq n \leq 2.5 \cdot 1 0^{5}$ .
$1 \leq q \leq 5 \cdot 1 0^{5}$ .
$1 \leq w \leq 1 0^{5}$ .
$1 \leq k < n$ ; các đỉnh đặc biệt thuộc $[2, n]$ và đôi một khác nhau trong một truy vấn.
Tổng $k$ qua mọi truy vấn không vượt quá $5 \cdot 1 0^{5}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 20$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

5
7
5

Giải thích: Với tập ${3, 4}$ , phá cạnh $1 - 2$ giá $5$ rẻ hơn xử lý hai nhánh riêng. Với ${3, 6}$ , hai đỉnh nằm ở hai nhánh gốc khác nhau nên chi phí tối ưu là $4 + 3 = 7$ . Khi $2$ cũng là đỉnh đặc biệt, phá $1 - 2$ vẫn đủ và tốn $5$ .

Cây ảo và DP cắt cạnh: Tiền xử lý LCA và trọng số nhỏ nhất trên đường từ một đỉnh lên tổ tiên bằng binary lifting. Với mỗi truy vấn, dựng cây ảo từ các đỉnh đặc biệt cùng gốc 1.
Cây ảo và DP cắt cạnh: Xét cạnh ảo từ cha p tới con u. Nếu quyết định cắt trên đoạn thật p-u, cách rẻ nhất là chọn cạnh nhẹ nhất của đoạn; gọi chi phí này là cut(u). Gọi sum(u) là tổng phương án tối ưu của các con ảo. Nếu u đặc biệt, bắt buộc ngăn toàn bộ cây con tại hoặc phía trên u, nên giá trị trả lên là cut(u). Nếu u không đặc biệt, có thể cắt một lần trên đoạn p-u hoặc xử lý riêng các nhánh con, nên lấy min(cut(u),sum(u)). Gốc không có cạnh phía trên, vì vậy đáp án là tổng các giá trị từ con của gốc.
Chứng minh đúng đắn: Mọi phương án hợp lệ trong cây con ảo của u thuộc đúng một trong hai loại: có cắt ít nhất một cạnh trên đoạn p-u, hoặc không cắt cạnh nào trên đoạn đó. Loại đầu tối ưu bằng cạnh nhẹ nhất cut(u) và tách đồng thời mọi đỉnh đặc biệt phía dưới. Loại sau buộc từng nhánh con giải quyết độc lập, tổng bằng sum(u); loại này không hợp lệ nếu chính u đặc biệt. Công thức DP xét đủ và lấy tốt nhất giữa các khả năng, nên đúng theo quy nạp hậu tự.
Độ phức tạp: Tiền xử lý O(n log n). Mỗi truy vấn tốn O(k log k); tổng thời gian O((n+Σk)log n), bộ nhớ O(n log n).