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

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

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

f[u, v] = \sum_{x\in S[v]}(d[u,x])^2 - \sum\limits_{x \notin S{\rm{[}}v{\rm{]}}} {{{(d{\rm{[}}u,x{\rm{]}})}^2}}

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

Dữ liệu vào:

  • Dòng đầu tiên là số ;
  • N-1 dòng tiếp theo thể hiện cạnh nối của cây bởi bộ ba số u_i, v_i, w_i có nghĩa là cạnh nối u_i\to v_i có trọng số là w_i ;
  • Dòng tiếp theo là số Q , số truy vấn;
  • Q dòng tiếp theo thể hiện các truy vấn bởi bộ hai số u, v có nghĩa là in ra kết quả của f[ơu, v]. Kết quả cần tính chia lấy dư cho 10^9 + 7$.

Dữ liệu ra:

  • Một dòng gồm Q số là kết quả của Q 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:

  • 1 \le N, Q \le 10^5; 1\le w_i \le 10^9 .