CF1260F Colored Tree

给定一棵有 $n$ 个节点的树，第 $i$ 个节点的颜色为 $h_i$。 树的价值定义为 $ \sum\limits_{h_i = h_j,\, 1 \le i < 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) $ 种不同的树）。

第一行包含一个整数 $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$），表示树中的一条边。保证这些边构成一棵树。

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

在第一个样例中，一共有四种不同的染色方式（即四棵不同的树）： - 所有节点颜色为 $\{1, 1, 1, 1\}$，此时树的价值为 $dis(1,2)+dis(1,3)+dis(1,4)+dis(2,3)+dis(2,4)+dis(3,4)=10$； - 节点颜色为 $\{1, 2, 1, 1\}$，此时树的价值为 $dis(1,3)+dis(1,4)+dis(3,4)=4$； - 节点颜色为 $\{1, 1, 1, 2\}$，此时树的价值为 $dis(1,2)+dis(1,3)+dis(2,3)=4$； - 节点颜色为 $\{1, 2, 1, 2\}$，此时树的价值为 $dis(1,3)+dis(2,4)=4$。 所有情况的价值和为 $10+4+4+4=22$。 由 ChatGPT 4.1 翻译