Colored Tree

题意翻译

给定一棵树，每个节点有一个颜色$h$，$h_i$为$[L_i,R_i]$内的一个整数。 现在，对于所有$\prod (R_i-L_i+1)$种不同的染色方案，求出下列式子之和： $$\sum_{h_i=h_j,1\leq i<j\leq n}dis(i,j)$$ $n\leq 10^5,1\leq L_i\leq R_i\leq 10^5$，答案对1e9+7取模。

题目描述

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 < 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).

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

22

说明

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 $ .