Али — младший брат Хамеда, у него завтра день рождения. Хамед хочет подарить брату подарок. Для этого он дал ему задачу по программированию и сказал, что если Али её решит, то он получит новенький ноутбук. Али ещё не такой талантливый программист как Хамед, и, хотя он обычно не жульничает, этот случай — исключение. Всё-таки на кону новенький ноутбук. Поэтому он решил в тайне от него попросить вас помочь ему. Пожалуйста, решите для Али следующую.
Вам дано взвешенное корневое дерево из n вершин. Вершина номер 1 является корнем дерева. Определим d(u, v) как сумму длин рёбер на кратчайшем пути между вершинами u и v. В частности, определим d(u, u) = 0. Также, определим S(v) для каждой вершины v как множество, содержащее все вершины u, такие, что d(1, u) = d(1, v) + d(v, u). Затем определим функцию f(u, v) по следующей формуле:
Ваша задача — вычислить f(u, v) для каждой из q данных пар вершин. Так как ответ может быть довольно большим, выведите его по модулю 109 + 7.
В первой строке входных данных дано целое число n (1 ≤ n ≤ 105), количество вершин дерева.
В каждой из следующих n - 1 строк записаны три целых числа через пробел — ai, bi, ci (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109), обозначающие, что между вершинами ai и bi есть ребро весом ci.
В следующей строке записано целое число q (1 ≤ q ≤ 105) — количество пар вершин.
В каждой из следующих q строк даны по два целых числа через пробел — ui, vi (1 ≤ ui, vi ≤ n), обозначающие, что вам требуется посчитать f(ui, vi).
Гарантируется, что данные ребра образуют дерево.
Выведите q строк. В i-й строке выведите значение f(ui, vi) по модулю 109 + 7.
5
1 2 1
4 3 1
3 5 1
1 3 1
5
1 1
1 5
2 4
2 1
3 5
10
1000000005
1000000002
23
1000000002
8
1 2 100
1 3 20
2 4 2
2 5 1
3 6 1
3 7 2
6 8 5
6
1 8
2 3
5 8
2 6
4 7
6 1
999968753
49796
999961271
999991235
999958569
45130
| Codeforces Round 282 (Div. 1) |
|---|
| Закончено |
