#861. SUMMAX5 - Tổng trên cây 5

Cho một cây có trọng số gồm đỉnh được đánh số từ đến , gốc tại đỉnh . Gọi là tổng trọng số trên đường đi ngắn nhất từ đến . Gọi là tập hợp các đỉnh thỏa mãn . Hàm số được định nghĩa như sau:

Hãy trả lời Q truy vấn về tính được đưa ra.

Dữ liệu vào:

• Dòng đầu tiên là số ;
• dòng tiếp theo thể hiện cạnh nối của cây bởi bộ ba số có nghĩa là cạnh nối có trọng số là ;
• Dòng tiếp theo là số , số truy vấn;
• dòng tiếp theo thể hiện các truy vấn bởi bộ hai số có nghĩa là in ra kết quả của 10^9 + 7$.

Dữ liệu ra:

• Một dòng gồm số là kết quả của truy vấn trên.

Ví dụ:

Dữ liệu vào:

5
1 2 1
4 3 1
3 5 1
1 3 1
5
1 1
1 5
2 4
2 1
3 5

Dữ liệu ra:

10
1000000005
1000000002
23
1000000002

Giới hạn:

• .