Saturday, December 3, 2016

Kitty's Calculations on a Tree

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.
  •  denotes the number of edges on the unique path between nodes  and .
Given  and  sets of  distinct nodes, can you help her calculate the expression for each set? For each set of nodes, print the value of the expression modulo  on a new line.
Input Format
The first line contains two space-separated integers describing the respective values of  (the number of nodes in tree ) and  (the number of sets).
Each of the  subsequent lines contains two space-separated integers,  and , describing an undirected edge between nodes  and .
The  subsequent lines define each set over two lines in the following format:
  1. The first line contains an integer, , denoting the size of the set.
  2. The second line contains  space-separated integers describing the set's elements.
Constraints
  • The sum of  over all  does not exceed .
  • All elements in each set are distinct.
Subtasks
  •  for  of the maximum score.
  •  for  of the maximum score.
  •  for  of the maximum score.
Output Format
Print  lines of output where each line  contains the expression for the  query, modulo .
Sample Input 0
7 3
1 2
1 3
1 4
3 5
3 6
3 7
2
2 4
1
5
3
2 4 5
Sample Output 0
16
0
106
Explanation 0
Tree  looks like this:
image
We perform the following calculations for  sets:
  • Set : Given set , the only pair we can form is , where . We then calculate the following answer and print it on a new line:
  • Set : Given set , we cannot form any pairs because we don't have at least two elements. Thus, we print  on a new line.
  • Set : Given set , we can form the pairs , and . We then calculate the following answer and print it on a new line:


Contact Geek Placement Preparation

Name

Email *

Message *