Kitty's Calculations on a Tree#11273
Kitty has a tree , consisting of nodes where each node is uniquely labeled from to . Her friend Alex gave her sets, where each set contains distinct nodes. Kitty needs to calculate the following expression on each set:
where:
denotes an unordered pair of nodes belonging to the set.
dist(u, v) denotes the number of edges on the unique (shortest) path between nodes and .
Given and sets of distinct nodes, calculate the expression for each set. For each set of nodes, print the value of the expression modulo 10^9 + 7 on a new line.
The first line contains two integers: the number n~(1 \le n \le 2 \cdot 10^5) of nodes in tree and the number of queries q~(1 \le q \le 10^5).
Each of the n - 1 subsequent lines contains two integers and b~(1 \le a, b \le n), that describe an undirected edge between nodes and .
The 2 \cdot q subsequent lines define each set over two lines in the following format:
The first line contains an integer — the size of the set;
The second line contains integers — the set's elements (1 \le k_i \le 10^5, the sum of k_i over all does not exceed 2 \cdot 10^5).
Print lines where each line contains the value of the expression for the -th query, modulo 10^9 + 7.
Primer 1