Colored Tree
Contest: Educational Codeforces Round 77 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, trees

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

Input format:
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.

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

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

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

Example input:
4
1 1
1 2
1 1
1 2
1 2
1 3
3 4

Example output:
22

Editorial:
Let's set the root as $$$1$$$. Define $$$lca(u,v)$$$ as the lowest common ancestor of vertices $$$u$$$ and $$$v$$$, $$$dep(u)$$$ as the depth of vertex $$$u$$$ $$$(dep(u) = dis(1,u))$$$. Obviously $$$dis(u,v) = dep(u) + dep(v) - 2 \times dep(lca(u,v))$$$.
The answer we want to calculate is $$$\sum_{G}{\sum_{h_{i} = h_{j},i < j}{dis(i,j)}}$$$ where $$$G$$$ represent all possible colorings of the tree.
We can enumerate the color $$$c$$$. For a fixed color $$$c$$$, we need to calculate $$$\sum_{l_{i} \leq c \leq r_{i} , l_{j} \leq c \leq r_{j}}{[dis(i,j) \times \prod_{k \neq i,j}{(r_{k} - l_{k} + 1)}]}$$$
Let $$$P = \prod_{1 \leq i \leq n}{(r_{i} - l_{i} + 1)} , g_{i} = r_{i} - l_{i} + 1$$$. Also denote $$$V(i)$$$ as a predicate which is true iff $$$l_{i} \leq c \leq r_{i}$$$.
$$$\begin{align} & \sum_{l_{i} \leq c \leq r_{i} , l_{j} \leq c \leq r_{j}}{[dis(i,j) \times \prod_{k \neq i,j}{(r_{k} - l_{k} + 1)}]} \\ = & \sum_{V(i) \land V(j)}{dep(i) \times \frac{P}{g_{i} \times g_{j}}} + \sum_{V(i) \land V(j)}{dep(j) \times \frac{P}{g_{i} \times g_{j}}} - 2 \times \sum_{V(i) \land V(j)}{dep(lca(i,j)) \times \frac{P}{g_{i} \times g_{j}}} \\ = & P \times (\sum_{V(i)}{\frac{dep(i)}{g_{i}}}) \times (\sum_{V(i)}{\frac{1}{g_{i}}}) - P \times \sum_{V(i)}{\frac{dep(i)}{g_{i}^2}} - 2P \times \sum_{V(i) \land V(j)}{dep(lca(i,j)) \times \frac{1}{g_{i} \times g_{j}}} \end{align}$$$
Now our problem is how to maintain this formula while enumerating the color $$$c$$$.
$$$P \times (\sum_{V(i)}{\frac{dep(i)}{g_{i}}}) \times (\sum_{V(i)}{\frac{1}{g_{i}}})$$$ can be easily maintained. For $$$\sum_{V(i) \land V(j)}{dep(lca(i,j)) \times \frac{1}{g_{i} \times g_{j}}}$$$, we can add $$$\frac{1}{g_{i}}$$$ to all vertices in path $$$i$$$ to $$$1$$$ (for each existing vertex $$$i$$$), and when new vertex is added, just calculate the sum of vertices on path from $$$i$$$ to $$$1$$$, minus the contribution of vertex $$$1$$$ (because there are $$$dep(u) + 1$$$ vertices in the path $$$u$$$ to $$$1$$$), and multiply it $$$\frac{1}{g_{i}}$$$. Similar operation can be used to handle the situation when some vertex disappears. All of this can be done with HLD.
Overall it's $$$O(c_{max} + nlog^2(n))$$$.