Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef and his friend John have not see each other for years. They are both are looking forward to meeting again in the city they both grew up in.

The city has N public squares that they can meet in.
The squares are numbered from 1 to N and are connected with N-1 roads. Each road has its own length

It is known that between two squares there is exactly one path that goes through the roads and squares such that no square appears in the path more than once. Roads do not intersect each other and it takes 0 time to pass through a square.

Chef and John have previously met in squares A_{1}, A_{2}, ..., A_{M} so they will meet in one of these squares again.
To make this meeting more adventurous they do not agree on the square beforehand. Rather, Chef will pick a random square C from this list of squares and John will independently pick a random square J from this list of squares. Both random choices will be taken uniformly over the list of squares.

In the day before the meeting, Chef spoke with his roomate about their plan and asked him to calculate the expected distance between squares that Chef and John randomly pick. Please remember that Chef's roommate knows neither C nor J. Help him calculate this expected distance.

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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space-separated integers N and M.

The next N-1 lines contain three space-separated integers V, U, and L describing a road with length L between squares V and U.

The final line of each case contains M space-separated integers A_{1}, A_{2}, ..., A_{M}.

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

For each test case, output a single line containing two integers numer and denom separated by a space. These indicate the fraction numer/denom giving expected distance between the squares randomly chosen by Chef and John. This fraction should be reduced so that gcd(numer, denom) = 1 and denom ≥ 1.

------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 50000$
$1 ≤ M ≤ N$
$1 ≤ V ≤ N$
$1 ≤ U ≤ N$
$1 ≤ L ≤ 10000$
$1 ≤ A_{i} ≤ N$
$The squares A_{i} are distinct.$
$Subtask #1 [40 points]: N ≤  1000$
$Subtask #2 [60 points]: No additional constraints$

----- Sample Input 1 ------ 
2
6 2
1 3 1
2 3 2
3 4 3
4 5 4
4 6 5
1 5
6 6
1 3 1
2 3 2
3 4 3
4 5 4
4 6 5
1 2 3 4 5 6
----- Sample Output 1 ------ 
4 1
29 6

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Mathematics

Probability


Solutions:
def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def append_count(graph, root, visited, A):
	s = []
	ss = []
	s.append(root)
	while s:
		root = s.pop()
		ss.append(root)
		visited[root] = True
		for node in graph[root][0]:
			if not visited[node[0]]:
				s.append(node[0])
	while ss:
		root = ss.pop()
		count = 0
		if root in A:
			count += 1
		for node in graph[root][0]:
			count += graph[node[0]][1]
		graph[root] = (graph[root][0], count)

def calculate(graph, root, visited, n, m):
	s = []
	ss = []
	s.append(root)
	while s:
		root = s.pop()
		ss.append(root)
		visited[root] = True
		for node in graph[root][0]:
			if not visited[node[0]]:
				s.append(node[0])
	visited = [False for i in range(n + 1)]
	B = [0 for i in range(n + 1)]
	while ss:
		ans = 0
		root = ss.pop()
		visited[root] = True
		for node in graph[root][0]:
			if visited[node[0]]:
				ans += node[1] * graph[node[0]][1] * (m - graph[node[0]][1])
				ans += B[node[0]]
		B[root] = ans
	return ans

def solve(graph, A, n, m):
	root = next(iter(A))
	visited = [False for i in range(n + 1)]
	append_count(graph, root, visited, A)
	visited = [False for i in range(n + 1)]
	ans = 2 * calculate(graph, root, visited, n, m)
	return (ans, m * m)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	graph = [([], 0) for i in range(n + 1)]
	for i in range(n - 1):
		(v, u, l) = map(int, input().split())
		graph[v][0].append((u, l))
		graph[u][0].append((v, l))
	A = set(map(int, input().split()))
	(x, y) = solve(graph, A, n, m)
	g = gcd(x, y)
	print(x // g, y // g)


import sys
sys.setrecursionlimit(1 << 17)
T = int(input())

def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x
for _ in range(T):
	(n, m) = map(int, input().split())
	g = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v, w) = map(int, input().split())
		g[u - 1].append((v - 1, w))
		g[v - 1].append((u - 1, w))
	marked = [False] * n
	for t in map(int, input().split()):
		marked[t - 1] = True
	sub = [0] * n

	def dfs(u, p):
		if marked[u]:
			sub[u] = 1
		res = 0
		for (v, w) in g[u]:
			if v == p:
				continue
			res += dfs(v, u)
			sub[u] += sub[v]
			sub_sup = m - sub[v]
			res += w * sub_sup * sub[v] * 2
		return res
	a = dfs(0, -1)
	b = m * m
	c = gcd(a, b)
	print(a // c, b // c)


import sys
import queue
global vis, m, adj, nes, num, ina, cost, n

def dfs(u):
	global vis, m, adj, nes, num, cost, ina, n
	vis[u] = True
	for v in adj[u]:
		if vis[v] == False:
			dfs(v)
			num += cost[v, u] * nes[v] * (m - nes[v])
			nes[u] += nes[v]
	if ina[u] == True:
		nes[u] += 1

def stackdfs(u):
	global vis, m, adj, nes, num, cost, ina, n
	cal = [0] * n
	s1 = list()
	s2 = list()
	s1.append(u)
	vis[u] = True
	while len(s1) != 0:
		v = s1.pop()
		if len(adj[v]) == 1 and vis[adj[v][0]] == True:
			cal[v] = 1
			if ina[v] == True:
				nes[v] += 1
		else:
			s2.append(v)
		for w in adj[v]:
			if vis[w] == False:
				s1.append(w)
				vis[w] = True
	while len(s2) != 0:
		v = s2.pop()
		for w in adj[v]:
			if cal[w] == 1:
				nes[v] += nes[w]
				num += cost[v, w] * nes[w] * (m - nes[w])
		if ina[v] == True:
			nes[v] += 1
		cal[v] = 1

def gcd(d, b):
	if b == 0:
		return d
	else:
		return gcd(b, d % b)
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	adj = []
	cost = dict()
	edg = dict()
	num = 0
	p = [-1] * n
	vis = [False] * n
	nes = [0] * n
	ina = [False] * n
	for i in range(n):
		adj.append([])
	for i in range(n - 1):
		(u, v, c) = map(int, sys.stdin.readline().split())
		u = u - 1
		v = v - 1
		adj[u].append(v)
		adj[v].append(u)
		cost[u, v] = c
		cost[v, u] = c
	a = []
	a = map(int, sys.stdin.readline().split())
	a = list(a)
	for i in range(m):
		ina[a[i] - 1] = True
	if m == 1:
		num = 0
	else:
		stackdfs(0)
	den = m * m
	flag = 0
	if den % 2 == 0:
		flag = 1
		den = den // 2
	if num >= den:
		z = gcd(num, den)
	else:
		z = gcd(den, num)
	num = num // z
	den = den // z
	if num == 0:
		den = 1
	if flag == 1:
		print(num, den)
	else:
		print(num * 2, den)