← 返回题目列表

Codeforces · 494/D

D. 生日

中文机器翻译题面 查看原题

阿里是哈米德的弟弟,明天是他的生日。哈米德希望他的兄弟能够赢得他的礼物,所以他给了他一个困难的编程问题,并告诉他如果他能成功解决它,他会给他一台全新的笔记本电脑。 Ali 还不是像 Hamed 那样非常有才华的程序员,虽然他通常不会作弊,但这一次是个例外。这是关于一台全新的笔记本电脑。于是他决定偷偷向你寻求帮助。请阿里解决这个问题。

给出了一个 n 顶点加权有根树。 1 号顶点是树的根。我们将 d(u, v) 定义为顶点 u 和 v 之间的最短路径上的边权重之和。具体来说,我们定义 d(u, u) = 0。另外,我们将每个顶点 v 的 S(v) 定义为包含所有顶点 u 的集合,使得 d(1, u) = d(1, v) + d(v, u)。然后使用以下公式定义函数 f(u, v):

$$f(u,v) = \sum_{x \in S(v)} d(u,x)^2 - \sum_{x \notin S(v)} d(u,x)^2$$

目标是计算给定的 q 个顶点对中的每一个的 f(u, v)。由于答案可能相当大,因此打印它对 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 的值。

示例

输入 #1

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

输出 #1

10
1000000005
1000000002
23
1000000002

输入 #2

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

输出 #2

999968753
49796
999961271
999991235
999958569
45130