CF1260F.Colored Tree

You're given a tree with $n$ vertices. The color of the $i$-th vertex is $h_{i}$.

The value of the tree is defined as $\sum\limits_{h_{i} = h_{j}, 1 \le i \lt j \le n}{dis(i,j)}$, where $dis(i,j)$ is the number of edges on the shortest path between $i$ and $j$.

The color of each vertex is lost, you only remember that $h_{i}$ can be any integer from $[l_{i}, r_{i}]$(inclusive). You want to calculate the sum of values of all trees meeting these conditions modulo $10^9 + 7$ (the set of edges is fixed, but each color is unknown, so there are $\prod\limits_{i = 1}^{n} (r_{i} - l_{i} + 1)$ different trees).

给你一棵包含 $n$ 个顶点的树。第 $i$ 个顶点的颜色为 $h_{i}$。

该树的值定义为 $\sum\limits_{h_{i} = h_{j}, 1 \le i \lt j \le n}{dis(i,j)}$，其中 $dis(i,j)$ 表示顶点 $i$ 与 $j$ 之间最短路径上的边数。

每个顶点的颜色均已丢失，你仅记得 $h_{i}$ 可以是区间 $[l_{i}, r_{i}]$（含端点）内的任意整数。你需要计算所有满足该条件的树的值之和，并对 $10^9 + 7$ 取模（树的边集固定，但各顶点颜色未知，因此共有 $\prod\limits_{i = 1}^{n} (r_{i} - l_{i} + 1)$ 棵不同的树）。

The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of vertices.

Then $n$ lines follow, each line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 10^5$) denoting the range of possible colors of vertex $i$.

Then $n - 1$ lines follow, each containing two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) denoting an edge of the tree. It is guaranteed that these edges form a tree.

第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 表示顶点的数量。

接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^5$），表示顶点 $i$ 可能的颜色取值范围。

然后是 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，且 $u \ne v$），表示树中的一条边。保证这些边构成一棵树。

Print one integer — the sum of values of all possible trees, taken modulo $10^9 + 7$.

输出一个整数——所有可能的树的权值之和，对 $10^9 + 7$ 取模。

In the first example there are four different ways to color the tree (so, there are four different trees):

• a tree with vertices colored as follows: $\lbrace 1,1,1,1 \rbrace$. The value of this tree is $dis(1,2)+dis(1,3)+dis(1,4)+dis(2,3)+dis(2,4)+dis(3,4) = 10$;
• a tree with vertices colored as follows: $\lbrace 1,2,1,1 \rbrace$. The value of this tree is $dis(1,3)+dis(1,4)+dis(3,4)=4$;
• a tree with vertices colored as follows: $\lbrace 1,1,1,2 \rbrace$. The value of this tree is $dis(1,2)+dis(1,3)+dis(2,3)=4$;
• a tree with vertices colored as follows: $\lbrace 1,2,1,2 \rbrace$. The value of this tree is $dis(1,3)+dis(2,4)=4$.

Overall the sum of all values is $10+4+4+4=22$.

在第一个例子中，有四种不同的方式为树染色（即，存在四棵不同的树）：

• 一棵顶点染色方案为 $\lbrace 1,1,1,1 \rbrace$ 的树。该树的值为 $dis(1,2)+dis(1,3)+dis(1,4)+dis(2,3)+dis(2,4)+dis(3,4) = 10$；
• 一棵顶点染色方案为 $\lbrace 1,2,1,1 \rbrace$ 的树。该树的值为 $dis(1,3)+dis(1,4)+dis(3,4)=4$；
• 一棵顶点染色方案为 $\lbrace 1,1,1,2 \rbrace$ 的树。该树的值为 $dis(1,2)+dis(1,3)+dis(2,3)=4$；
• 一棵顶点染色方案为 $\lbrace 1,2,1,2 \rbrace$ 的树。该树的值为 $dis(1,3)+dis(2,4)=4$。

所有树的值之和为 $10+4+4+4=22$。