You have a rooted tree with $n$ vertices numbered from $\mbox{1}$ through $n$ where the root is vertex $\mbox{1}$. 

You are given $m$ triplets, the $j^{th}$ triplet is denoted by three integers $u_j,v_j,c_j$. The $j^{th}$ triplet represents a simple path in the tree with endpoints in $u_i$ and $v_i$ such that $u_j$ is ancestor of $v_j$. The cost of the path is $c_j$. 

You have to select a subset of the paths such that the sum of path costs is maximum and the $i^{\mbox{th}}$ edge of the tree belongs to at most $d_i$ paths from the subset. Print the sum as the output.

Input Format

The first line contains a single integer, $\mathbf{T}$, denoting the number of testcases. Each testcase is defined as follows:

The first line contains two space-separated integers, $n$ (the number of vertices) and $m$ (the number of paths), respectively.
Each line $\boldsymbol{i}$ of the $n-1$ subsequent lines contains three space-separated integers describing the respective values of $a_i$, $b_i$, and $d_i$ where ($a_i$, $b_i$) is an edge in the tree and $d_i$ is maximum number of paths which can include this edge.
Each line of the $m$ subsequent lines contains three space-separated integers describing the respective values of $u_j$, $v_j$, and $c_j$ ($u_j\neq v_j$) that define the $j^{th}$ path and its cost.

Constraints

Let $\mbox{M}$ be the sum of $m$ over all the trees. 
Let $\mbox{D}$ be the sum of $n\times m$ over all the trees.
$1\leq T\leq10^3$  
$1\leq M,m\leq10^3$  
$1\leq D,n\leq5\times10^5$  
$1\leq c_i\leq10^9$  
$1\leq d_j\leq m$

Output Format

You must print $\mathbf{T}$ lines, where each line contains a single integer denoting the answer for the corresponding testcase.

Sample Input
1
8 8
1 2 3
1 3 1
2 4 5
2 5 1
2 6 1
3 7 2
4 8 1
1 2 3
2 8 5
1 8 7
1 5 8
1 6 10
3 7 5
1 7 6
1 7 6

Sample Output
37

Explanation

One of the possible subsets contains paths $1,2,4,5,6,7$. Its total cost is $3+5+8+10+5+6=37$.

Source: hackerrank | Difficulty: HARD
Tags: Graph algorithms


Solutions:
import collections
import random
import itertools

class Trial:
	routes = None

	def __init__(self, remaining, used_routes=None, value=0):
		self.remaining = remaining
		self.used_routes = set() if used_routes is None else used_routes
		self.value = value

	def can_add(self, route):
		if route[2] in self.used_routes:
			return False
		for node_id in route[1]:
			if self.remaining[node_id] == 0:
				return False
		return True

	def add(self, route):
		self.used_routes.add(route[2])
		self.value += route[0]
		for node_id in route[1]:
			self.remaining[node_id] -= 1

	def add_list(self, routes):
		for route in routes:
			if self.can_add(route):
				self.add(route)

	def add_list_double(self, route1, route2):
		self.add_list(route1)
		self.add_list(route2)

class Collect:

	def __init__(self, routes, available):
		self.available = available
		Trial.routes = routes
		self.routes = routes
		self.used_routes = set(range(len(self.routes)))
		self.value = 0

	def process(self):
		trial = []
		max_val = 0
		self.routes.sort(key=lambda x: -x[0])
		my_trial = Trial(dict(self.available))
		my_trial.add_list(self.routes)
		max_val = max(max_val, my_trial.value)
		trial.append(my_trial)
		my_trial = Trial(dict(self.available))
		my_trial.add_list(sorted(self.routes, key=lambda x: (len(x[1]), -x[0])))
		max_val = max(max_val, my_trial.value)
		trial.append(my_trial)
		my_trial = Trial(dict(self.available))
		my_trial.add_list(sorted(self.routes, key=lambda x: -x[0] / len(x[1])))
		max_val = max(max_val, my_trial.value)
		trial.append(my_trial)
		limit = 100
		start = self.routes[0:limit]
		remaining = self.routes[limit:]
		for i in range(20):
			random.shuffle(start)
			my_trial = Trial(dict(self.available))
			my_trial.add_list_double(start, remaining)
			max_val = max(max_val, my_trial.value)
		return max_val

class Solution:

	def __init__(self):
		self.parents = {}
		(self.nodes, self.edges) = get_int_list(input())
		self.edge_list = []
		self.remaining = {}
		self.adj_list = {i: [] for i in range(1, self.nodes + 1)}
		for i in range(self.nodes - 1):
			edge = get_int_list(input())
			self.remaining[edge[1]] = edge[2]
			self.edge_list.append(edge)
			self.adj_list[edge[0]].append((edge[1], edge[2]))
			self.adj_list[edge[1]].append((edge[0], edge[2]))
		self.path_list = []
		for i in range(self.edges):
			self.path_list.append(get_int_list(input()))
		self.graph = None
		self.root = None

	def process_graph(self):
		queue = collections.deque()
		queue.append(1)
		visited_set = {1}
		while len(queue) > 0:
			node_id = queue.popleft()
			for (child_id, weight) in self.adj_list[node_id]:
				if child_id not in visited_set:
					self.parents[child_id] = node_id
					self.remaining[child_id] = weight
					visited_set.add(child_id)
					queue.append(child_id)

	def get_path(self, origin, dest):
		route = []
		node_id = origin
		while node_id != dest:
			route.append(node_id)
			node_id = self.parents[node_id]
		return route

	def get_path_routes(self):
		path_list_old = self.path_list
		self.path_list = []
		for (path_id, path) in enumerate(path_list_old):
			route = self.get_path(path[1], path[0])
			self.path_list.append((path[2], route, path_id))

	def calculate(self):
		self.process_graph()
		self.get_path_routes()
		collect = Collect(self.path_list, self.remaining)
		return collect.process()

def main():
	cases = int(input())
	for i in range(cases):
		my_object = Solution()
		print(my_object.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


import collections
import random
import itertools

class Trial:
	routes = None

	def __init__(self, remaining, used_routes=None, value=0):
		self.remaining = remaining
		self.used_routes = set() if used_routes is None else used_routes
		self.value = value

	def can_add(self, route):
		if route[2] in self.used_routes:
			return False
		for node_id in route[1]:
			if self.remaining[node_id] == 0:
				return False
		return True

	def add(self, route):
		self.used_routes.add(route[2])
		self.value += route[0]
		for node_id in route[1]:
			self.remaining[node_id] -= 1

	def add_list(self, routes):
		for route in routes:
			if self.can_add(route):
				self.add(route)

	def add_list_double(self, route1, route2):
		self.add_list(route1)
		self.add_list(route2)

class Collect:

	def __init__(self, routes, available):
		self.available = available
		Trial.routes = routes
		self.routes = routes
		self.used_routes = set(range(len(self.routes)))
		self.value = 0

	def process(self):
		trial = []
		max_val = 0
		self.routes.sort(key=lambda x: -x[0])
		my_trial = Trial(dict(self.available))
		my_trial.add_list(self.routes)
		max_val = max(max_val, my_trial.value)
		trial.append(my_trial)
		my_trial = Trial(dict(self.available))
		my_trial.add_list(sorted(self.routes, key=lambda x: (len(x[1]), -x[0])))
		max_val = max(max_val, my_trial.value)
		trial.append(my_trial)
		my_trial = Trial(dict(self.available))
		my_trial.add_list(sorted(self.routes, key=lambda x: -x[0] / len(x[1])))
		max_val = max(max_val, my_trial.value)
		trial.append(my_trial)
		limit = 100
		start = self.routes[0:limit]
		remaining = self.routes[limit:]
		for i in range(20):
			random.shuffle(start)
			my_trial = Trial(dict(self.available))
			my_trial.add_list_double(start, remaining)
			max_val = max(max_val, my_trial.value)
		return max_val

class Solution:

	def __init__(self):
		self.parents = {}
		(self.nodes, self.edges) = get_int_list(input())
		self.edge_list = []
		self.remaining = {}
		self.adj_list = {i: [] for i in range(1, self.nodes + 1)}
		for i in range(self.nodes - 1):
			edge = get_int_list(input())
			self.remaining[edge[1]] = edge[2]
			self.edge_list.append(edge)
			self.adj_list[edge[0]].append((edge[1], edge[2]))
			self.adj_list[edge[1]].append((edge[0], edge[2]))
		self.path_list = []
		for i in range(self.edges):
			self.path_list.append(get_int_list(input()))
		self.graph = None
		self.root = None

	def process_graph(self):
		queue = collections.deque()
		queue.append(1)
		visited_set = {1}
		while len(queue) > 0:
			node_id = queue.popleft()
			for (child_id, weight) in self.adj_list[node_id]:
				if child_id not in visited_set:
					self.parents[child_id] = node_id
					self.remaining[child_id] = weight
					visited_set.add(child_id)
					queue.append(child_id)

	def get_path(self, origin, dest):
		route = []
		node_id = origin
		while node_id != dest:
			route.append(node_id)
			node_id = self.parents[node_id]
		return route

	def get_path_routes(self):
		path_list_old = self.path_list
		self.path_list = []
		for (path_id, path) in enumerate(path_list_old):
			route = self.get_path(path[1], path[0])
			self.path_list.append((path[2], route, path_id))

	def calculate(self):
		self.process_graph()
		self.get_path_routes()
		collect = Collect(self.path_list, self.remaining)
		return collect.process()

def main():
	cases = int(input())
	for i in range(cases):
		my_object = Solution()
		print(my_object.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()