You are a given a tree of N vertices. The i-th vertex has two things assigned to it — a value A_{i} and a range [L_{i}, R_{i}]. It is guaranteed that L_{i} ≤ A_{i} ≤ R_{i}.

You perform the following operation exactly once:
Pick a (possibly empty) subset S of vertices of the tree. S must satisfy the additional condition that no two vertices in S are directly connected by an edge, i.e, it is an [independent set].
Then, for each x \in S, you can set A_{x} to any value in the range [L_{x}, R_{x}] (endpoints included).

Your task is to minimize the value of \sum |A_{u} - A_{v}| over all unordered pairs (u, v) such that u and v are connected by an edge.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N, the number of vertices.
- The next N lines describe the values of the vertices. The i-th of these N lines contains three space-separated integers L_{i}, A_{i}, and R_{i} respectively
- The next N-1 lines describe the edges. The i-th of these N-1 lines contains two space-separated integers u_{i} and v_{i}, denoting an edge between u_{i} and v_{i}.

------ Output Format ------ 

For each test case, output on a new line the minimum possible value as described in the statement.

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

$1 ≤ T ≤ 10^{4}$
$3 ≤ N ≤ 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
$u_{i} \neq v_{i}$ for each $1 ≤ i ≤ N-1$
$1 ≤ L_{i} ≤ A_{i} ≤ R_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
3
1 1 1
2 3 3
3 3 3
1 2
1 3
4
3 3 4
1 3 5
2 2 2
2 2 2
1 2
2 3
2 4

----- Sample Output 1 ------ 
3
1
----- explanation 1 ------ 
Test case $1$: Set the value of $A_{2}$ to $2$. The answer is $|A_{1} - A_{2}| + |A_{1} - A_{3}| = |1 - 2| + |1 - 3| = 3$.

Test case $2$: Set the value of $A_{2}$ to $2$. The answer is $|A_{1} - A_{2}| + |A_{2} - A_{3}| + |A_{2} - A_{4}| = |3 - 2| + |2 - 2| + |2 - 2| = 1$.

Difficulty: VERY_HARD
Tags: Tree algorithms

Graph algorithms

Data structures

Dynamic programming
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(2 * 10 ** 5)
inp = lambda : list(map(int, input().split()))

def dfs(p, prev, took):
	if dp[p][took] != -1:
		return dp[p][took]
	if prev:
		if took == 0:
			pval = a[prev - 1]
		elif took == 1:
			pval = l[prev - 1]
		elif took == 2:
			pval = r[prev - 1]
		else:
			pval = median[prev - 1]
	ans = float('inf')
	v = 0
	for i in child[p]:
		if i == prev:
			continue
		v += dfs(i, p, 0)
	if prev:
		v += abs(a[p - 1] - pval)
	ans = min(ans, v)
	if took == 0:
		(v1, v2) = (0, 0)
		for i in child[p]:
			if i == prev:
				continue
			v1 += dfs(i, p, 1)
			v2 += dfs(i, p, 2)
		if prev:
			v1 += abs(l[p - 1] - pval)
		if prev:
			v2 += abs(r[p - 1] - pval)
		ans = min(ans, v1, v2)
		if l[p - 1] <= median[p - 1] and r[p - 1] >= median[p - 1]:
			v = 0
			for i in child[p]:
				if i == prev:
					continue
				v += dfs(i, p, 3)
			if prev:
				v += abs(median[p - 1] - pval)
			ans = min(ans, v)
	dp[p][took] = ans
	return ans
for T in range(int(input())):
	n = int(input())
	(l, r, a) = ([], [], [])
	for i in range(n):
		(u, v, w) = inp()
		l.append(u)
		r.append(w)
		a.append(v)
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = inp()
		child[u].append(v)
		child[v].append(u)
	median = []
	for i in range(1, n + 1):
		take = []
		for j in child[i]:
			take.append(a[j - 1])
		take.sort()
		median.append(take[len(take) // 2])
	dp = [[-1, -1, -1, -1] for i in range(n + 1)]
	ans = dfs(1, 0, 0)
	print(ans)