#5445. Kết nối trong tập đỉnh (CONNECTSET)

Trong một hệ thống mạng nội bộ của một doanh nghiệp lớn, các máy chủ được kết nối với nhau theo dạng cây để đảm bảo việc định tuyến luôn ổn định và không dư thừa. Mỗi máy chủ tương ứng với một đỉnh của cây, và mỗi kết nối vật lý giữa hai máy chủ tương ứng với một cạnh.

Do nhu cầu kiểm thử hệ thống, bộ phận kỹ thuật thường xuyên chọn ra một tập các máy chủ và cần biết mức độ "kết nối nội bộ" của tập này. Cụ thể, hai máy chủ và trong được xem là kết nối trên nếu có một đường đi trong cây nối và mà tất cả các máy chủ trên đường đi đều thuộc chính tập .

Mức độ kết nối cho biết có bao nhiêu cặp máy chủ trong tập thật sự có thể liên lạc trực tiếp với nhau mà không cần thoát ra ngoài tập. Nhiệm vụ của bạn là, với mỗi truy vấn, hãy tính xem tập được cho có bao nhiêu cặp như vậy.

Cho một cây gồm đỉnh đánh số . Cạnh thứ nối hai đỉnh khác nhau .

Chọn một tập đỉnh (các phần tử đôi một khác nhau). Với hai đỉnh khác nhau , nói rằng và kết nối trên nếu tồn tại một đường đi trên cây từ đến mà mọi đỉnh trên đường đi đều thuộc .

Độ kết nối của được định nghĩa là số cặp thoả mãn:

1. và ;

2. ;

3. và kết nối trên .

Bạn được cho truy vấn, mỗi truy vấn cho một tập . Hãy tính độ kết nối của cho từng truy vấn.

Dữ liệu:

• Dòng đầu chứa một số nguyên .

• dòng tiếp theo, dòng thứ chứa hai số nguyên .

• Dòng tiếp theo chứa một số nguyên .

• dòng tiếp theo, dòng thứ mô tả truy vấn thứ : trước hết là một số nguyên , sau đó là số ; dãy các phần tử đôi một phân biệt).

Dữ liệu bảo đảm đồ thị là một cây; tổng trên tất cả truy vấn .

Kết quả: Gồm dòng, dòng thứ là độ kết nối của trong truy vấn thứ .

Ví dụ:

Dữ liệu:

7
1 2
1 3
1 5
2 7
4 6
4 7
6
1 1
2 1 2
4 1 2 3 4
5 1 2 4 6 7
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7

Kết quả:

0
1
3
10
7
21

Giới hạn:

• Subtask 1 ( số điểm): .

• Subtask 2 ( số điểm): .

• Subtask 3 ( số điểm): Mỗi truy vấn có .

• Subtask 4 ( số điểm): Không ràng buộc bổ sung.