
Kitty's Calculations on a Tree
The first line contains an integer,k , the size of the set. The second line contains k space-separated integers, the set's elements.
# Enter your code here. Read input from STDIN. Print output to STDOUT
from itertools import combinations
from queue import Queue
from collections import defaultdict as dd,deque
def find_shortest_path(graph, start, end):
dist = {start: [start]}
que = deque()
que.append(start)
while len(que):
at = que.popleft()
for next in graph[at]:
if next not in dist:
dist[next] = dist[at]+[next]
que.append(next)
return dist.get(end)
def add(d,a,b):
d[a].append(b)
d[b].append(a)
if __name__=='__main__':
d=dd(list)
t,q=map(int,input().split())
for _ in range(t-1):
a,b=map(int,input().split())
add(d,a,b)
for _ in range(q):
k=int(input())
l=list(map(int,input().split()))
if len(l)>1:
s=list(combinations(l,2))
sum=0
for j in s:
u,v=j
p=find_shortest_path(d,u,v)
dist=len(p)-1
sum=sum+(u*v*dist)
result=sum%((10**9)+7)
print(result)
else:
print(0)
continue