There are N cities in Byteland numbered 1 to N with city 1 as the capital. The road network of Byteland has a tree structure. All the roads are bi-directional. Alice and Bob are secret agents working for the Bytelandian Security Agency (BSA). Each secret agent is assigned a random city each month, where he/she must be stationed for the complete month. At the end of each month, they come to the capital to submit their reports to the head of BSA. They always take the shortest path from their city to the capital. If Alice is assigned city A and Bob is assigned city B then they meet at a city C which is common to both their routes to the capital and then travel together from C to the capital.

Alice and Bob wish to spend maximum time together in any trip. So for any pair of assigned cities (A,B) they meet at a city C such that C is the farthest city from the capital and appears in the shortest path from capital to A and capital to B. Since this happens each month they compute this for each pair of assigned cities (A,B) and store it in a matrix M, where M[A][B] = C, the city where they meet.

The importance of a city C(according to Alice and Bob), Im(C) is defined as the number of times C appears in their matrix M. Alice and Bob are interested in finding the importance of each city. Since this output can be large, output the sum S defined as S = (sum i=1 to N) i*Im(i) modulo 1000000007. 

------ Input ------ 

First line of input contains an integer t (t≤25), the number of test cases. Each test case starts with an integer N (1≤N≤10000), the number of cities

The next N-1 lines contain two space separated integers u v (1≤u,v≤N) denoting a road from u to v.

------ Output ------ 

For each test case output the required sum S

----- Sample Input 1 ------ 
3
5
1 2
1 3
2 4
2 5
3
1 2
1 3
1
----- Sample Output 1 ------ 
41
12
1
----- explanation 1 ------ 
For the first test case, the matrix M is:
1 1 1 1 1
1 2 1 2 2
1 1 3 1 1
1 2 1 4 2
1 2 1 2 5

and the corresponding importance array is: 15 7 1 1 1 
so the required sum is 1*15 + 2*7 + 3*1 + 4*1 + 5*1 = 41
For the second test case, the matrix M is:
1 1 1
1 2 1
1 1 3
and so the Importance array is: 7 1 1 
So the required sum is 1*7 + 2*1 + 3*1 = 12

For the third test case, there is only one city, so the Matrix M just has one entry 1, so S = 1

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Tree algorithms

Mathematics

Data structures

Tree queries
Skill types: Data structures

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 5)

def dfs(node):
	visited.add(node)
	cur = []
	cur_sum = 0
	for child in dct[node]:
		if child not in visited:
			a = dfs(child) + 1
			cur_sum += a
			cur.append(a)
	childs_dct[node] = cur
	return cur_sum

def soln(dct, childs_dct):
	mod = 1000000007
	dfs(1)
	ans = [0]
	for i in range(1, n + 1):
		child_list = childs_dct[i]
		count = 0
		for j in range(len(child_list)):
			a = child_list[j]
			count += a * 2
			for k in range(j + 1, len(child_list)):
				b = child_list[k]
				count += a * b * 2
				count %= mod
		ans.append(count + 1)
	a = 0
	for i in range(n + 1):
		a += i * ans[i]
		a %= mod
	print(a)
for _ in range(int(input())):
	n = int(input())
	dct = {i: [] for i in range(1, n + 1)}
	childs_dct = dct.copy()
	visited = set()
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		dct[a].append(b)
		dct[b].append(a)
	soln(dct, childs_dct)


import sys
sys.setrecursionlimit(100000)

def dfs(node):
	if node in visited:
		childs_dct[node] = []
		return 0
	childs = dct[node]
	count = []
	s = 0
	visited.add(node)
	for child in childs:
		if child not in visited:
			a = dfs(child) + 1
			s += a
			count.append(a)
	childs_dct[node] = count
	return s

def solve():
	try:
		if dct == {}:
			print(1)
			return
		mod = 1000000007
		dfs(1)
		ans = [0]
		for i in range(1, n + 1):
			child_list = childs_dct[i]
			count = 0
			for j in range(len(child_list)):
				a = child_list[j]
				count += a * 2
				for k in range(j + 1, len(child_list)):
					b = child_list[k]
					count += a * b * 2
					count %= mod
			ans.append(count + 1)
		a = 0
		for i in range(n + 1):
			a += i * ans[i]
			a %= mod
		print(a)
	except Exception as e:
		print(e)
for _ in range(int(input())):
	n = int(input())
	dct = {}
	childs_dct = {i: [] for i in range(1, n + 1)}
	visited = set()
	for i in range(n - 1):
		(a, b) = list(map(int, input().split()))
		(a, b) = (min(a, b), max(a, b))
		if a not in dct:
			dct[a] = [b]
		else:
			dct[a].append(b)
		if b not in dct:
			dct[b] = [a]
		else:
			dct[b].append(a)
	solve()


import sys
sys.setrecursionlimit(100000)

def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
from collections import Counter

def dfs(node):
	if node in visited:
		childs_dct[node] = []
		return 0
	childs = dct[node]
	count = []
	s = 0
	for child in childs:
		if child not in visited:
			visited.add(node)
			a = 0
			a += dfs(child) + 1
			s += a
			count.append(a)
	childs_dct[node] = count
	return s

def main():
	try:
		if dct == {}:
			print(1)
			return
		mod = 1000000007
		dfs(1)
		ans = [0]
		for i in range(1, n + 1):
			child_list = childs_dct[i]
			count = 0
			for j in range(len(child_list)):
				a = child_list[j]
				count += a * 2
				for k in range(j + 1, len(child_list)):
					b = child_list[k]
					count += a * b * 2
					count %= mod
				count %= mod
			ans.append(count + 1)
		a = 0
		for i in range(n + 1):
			a += i * ans[i]
			a %= mod
		print(a)
	except Exception as e:
		print(e)
t = int(input())
for _ in range(t):
	n = int(input())
	dct = {}
	childs_dct = {i: [] for i in range(1, n + 1)}
	visited = set()
	for i in range(n - 1):
		(a, b) = integer_list()
		(a, b) = (min(a, b), max(a, b))
		if a not in dct:
			dct[a] = [b]
		else:
			dct[a].append(b)
		if b not in dct:
			dct[b] = [a]
		else:
			dct[b].append(a)
	main()