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 < 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/A

N/A

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