Forever Young

题号：NC252837
时间限制：C/C++/Rust/Pascal 7秒，其他语言14秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

I remember what someone said to me a long time ago, "The path you choose, even if you walk on your knees, you have to finish it". Friends, although the world is getting more and more impetuous, as long as we can persist in our efforts for the sake of our once pure dreams and moving motives, we can remain true to ourselves all the way, no matter what others do.

As a retired contestant, Colin hopes that all participants will always have a young heart and an eternal love for algorithms and competitive programming.

Given a tree $T$ consisting of $n$ vertices (indexed from $1$ to $n$ ). Vertex $1$ is the root.

We define that vertex $u$ is an ancestor of vertex $v$ if and only if $u$ is on the path from $v$ to the root.

Then we define $subtree_u$ as the set of all vertices $v$ satisfies that $u$ is an ancestor of $v$ .

Now Colin and Eva give each node $u$ two integer weights $c_u,e_u$ , then we define :

$ans_u=\sum_{x\in subtree_u}\sum_{y\in subtree_u} \min\{|c_x-c_y|,|e_x-e_y|\} \mod 10^9+7$

Please calculate $ans_u$ for each vertex $u\in [1, n]$ .

输入描述:

The first line contains a single integer  , representing the number of vertices.

For the following  lines, each line contains two integers  , representing that there is an edge connecting vertex  and vertex  . It's guaranteed that the given edges form a tree.

For the following  lines, the -th line contains two integers  , representing the two weights of vertex .

输出描述:

Output  lines.

For -th line output a single integer  .

示例1

输入

复制

输出

复制