Birthday

题意翻译

给定一棵 n($1 \leq n\leq 10^5$) 个顶点的带边权的树，以点 1 为根。定义 $d(u,v)$ 为 u 到 v 的简单路径上所有边的权值之和。特别地，我们有 $d(u,u)=0$。 接着对节点 v 定义集合 S(v)，表示所有满足 $d(1,u)=d(1,v)+d(v,u)$的点 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 对 $u,v$ 计算出 $f(u,v)$ 的值。由于答案可能过大，请模 $10^9+7$ 输出。

题目描述

Ali is Hamed's little brother and tomorrow is his birthday. Hamed wants his brother to earn his gift so he gave him a hard programming problem and told him if he can successfully solve it, he'll get him a brand new laptop. Ali is not yet a very talented programmer like Hamed and although he usually doesn't cheat but this time is an exception. It's about a brand new laptop. So he decided to secretly seek help from you. Please solve this problem for Ali. An $ n $ -vertex weighted rooted tree is given. Vertex number $ 1 $ is a root of the tree. We define $ d(u,v) $ as the sum of edges weights on the shortest path between vertices $ u $ and $ v $ . Specifically we define $ d(u,u)=0 $ . Also let's define $ S(v) $ for each vertex $ v $ as a set containing all vertices $ u $ such that $ d(1,u)=d(1,v)+d(v,u) $ . Function $ f(u,v) $ is then defined using the following formula: The goal is to calculate $ f(u,v) $ for each of the $ q $ given pair of vertices. As the answer can be rather large it's enough to print it modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

Ali is Hamed's little brother and tomorrow is his birthday. Hamed wants his brother to earn his gift so he gave him a hard programming problem and told him if he can successfully solve it, he'll get him a brand new laptop. Ali is not yet a very talented programmer like Hamed and although he usually doesn't cheat but this time is an exception. It's about a brand new laptop. So he decided to secretly seek help from you. Please solve this problem for Ali. An $ n $ -vertex weighted rooted tree is given. Vertex number $ 1 $ is a root of the tree. We define $ d(u,v) $ as the sum of edges weights on the shortest path between vertices $ u $ and $ v $ . Specifically we define $ d(u,u)=0 $ . Also let's define $ S(v) $ for each vertex $ v $ as a set containing all vertices $ u $ such that $ d(1,u)=d(1,v)+d(v,u) $ . Function $ f(u,v) $ is then defined using the following formula: The goal is to calculate $ f(u,v) $ for each of the $ q $ given pair of vertices. As the answer can be rather large it's enough to print it modulo $ 10^{9}+7 $ .

输出格式

Ali is Hamed's little brother and tomorrow is his birthday. Hamed wants his brother to earn his gift so he gave him a hard programming problem and told him if he can successfully solve it, he'll get him a brand new laptop. Ali is not yet a very talented programmer like Hamed and although he usually doesn't cheat but this time is an exception. It's about a brand new laptop. So he decided to secretly seek help from you. Please solve this problem for Ali. An $ n $ -vertex weighted rooted tree is given. Vertex number $ 1 $ is a root of the tree. We define $ d(u,v) $ as the sum of edges weights on the shortest path between vertices $ u $ and $ v $ . Specifically we define $ d(u,u)=0 $ . Also let's define $ S(v) $ for each vertex $ v $ as a set containing all vertices $ u $ such that $ d(1,u)=d(1,v)+d(v,u) $ . Function $ f(u,v) $ is then defined using the following formula: The goal is to calculate $ f(u,v) $ for each of the $ q $ given pair of vertices. As the answer can be rather large it's enough to print it modulo $ 10^{9}+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