Parsa has a humongous tree on $n$ vertices.

On each vertex $v$ he has written two integers $l_v$ and $r_v$.

To make Parsa's tree look even more majestic, Nima wants to assign a number $a_v$ ($l_v \le a_v \le r_v$) to each vertex $v$ such that the beauty of Parsa's tree is maximized.

Nima's sense of the beauty is rather bizarre. He defines the beauty of the tree as the sum of $|a_u - a_v|$ over all edges $(u, v)$ of the tree.

Since Parsa's tree is too large, Nima can't maximize its beauty on his own. Your task is to find the maximum possible beauty for Parsa's tree.


-----Input-----

The first line contains an integer $t$ $(1\le t\le 250)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(2\le n\le 10^5)$ — the number of vertices in Parsa's tree.

The $i$-th of the following $n$ lines contains two integers $l_i$ and $r_i$ $(1 \le l_i \le r_i \le 10^9)$.

Each of the next $n-1$ lines contains two integers $u$ and $v$ $(1 \le u , v \le n, u\neq v)$ meaning that there is an edge between the vertices $u$ and $v$ in Parsa's tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case print the maximum possible beauty for Parsa's tree.


-----Examples-----

Input
3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6
Output
7
8
62


-----Note-----

The trees in the example:

In the first test case, one possible assignment is $a = \{1, 8\}$ which results in $|1 - 8| = 7$.

In the second test case, one of the possible assignments is $a = \{1, 5, 9\}$ which results in a beauty of $|1 - 5| + |5 - 9| = 8$

Difficulty: MEDIUM_HARD
Tags: Graph traversal

Greedy algorithms

Tree algorithms

Dynamic programming

Divide and conquer
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
def some_random_function():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function5():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
import os, sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		l = [tuple(map(int, input().split())) for _ in range(n)]
		path = [[] for _ in range(n)]
		for _ in range(n - 1):
			(u1, v1) = map(lambda xx: int(xx) - 1, input().split())
			path[u1].append(v1)
			path[v1].append(u1)
		(st, poi, visi) = ([0], [0] * n, [1] + [0] * (n - 1))
		dp = [[0] * n for _ in range(2)]
		while len(st):
			(x, y) = (st[-1], path[st[-1]])
			if poi[x] != len(y) and visi[y[poi[x]]]:
				poi[x] += 1
			if poi[x] == len(y):
				st.pop()
				if len(st):
					z = st[-1]
					for rr in range(2):
						dp[rr][z] += max(dp[0][x] + abs(l[x][0] - l[z][rr]), dp[1][x] + abs(l[x][1] - l[z][rr]))
			else:
				i = y[poi[x]]
				visi[i] = 1
				st.append(i)
				poi[x] += 1
		print(max(dp[0][0], dp[1][0]))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def some_random_function1():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function2():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function3():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function4():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function6():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function7():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function8():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
main()


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
sys.setrecursionlimit(10000000)

def dfs(i, p, l0, l1, dp0, dp1, adj):
	for j in adj[i]:
		if j != p:
			dfs(j, i, l0, l1, dp0, dp1, adj)
	dp0[p] += max(dp0[i] + abs(l0[p] - l0[i]), dp1[i] + abs(l0[p] - l1[i]))
	dp1[p] += max(dp0[i] + abs(l1[p] - l0[i]), dp1[i] + abs(l1[p] - l1[i]))

def solve():
	n = int(input())
	(l0, l1) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(1, n + 1):
		(l0[i], l1[i]) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	(dp1, dp0) = ([0] * (n + 1), [0] * (n + 1))
	dfs(1, 0, l0, l1, dp0, dp1, adj)
	print(max(dp0[1], dp1[1]))
for _ in range(int(input())):
	solve()


import io
import os
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify
from math import gcd, inf
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def solve(N, LR, edges):
	graph = [[] for i in range(N)]
	for (u, v) in edges:
		graph[u].append(v)
		graph[v].append(u)
	dp = [-1] * (2 * N)

	@bootstrap
	def dfs(u, p, i):
		if dp[2 * u + i] == -1:
			a = LR[u][i]
			best = 0.0
			for v in graph[u]:
				if v != p:
					yield dfs(v, u, 0)
					yield dfs(v, u, 1)
					best += max(abs(a - LR[v][0]) + dp[2 * v + 0], abs(a - LR[v][1]) + dp[2 * v + 1])
			dp[2 * u + i] = best
		yield
	root = 0
	dfs(root, -1, 0)
	dfs(root, -1, 1)
	return int(max(dp[2 * root + 0], dp[2 * root + 1]))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	LR = [[int(x) for x in input().split()] for i in range(N)]
	edges = [[int(x) - 1 for x in input().split()] for i in range(N - 1)]
	ans = solve(N, LR, edges)
	print(ans)


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	n = int(input())
	a = [0] + [list(map(int, input().split())) for i in range(n)]
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	dp = [[0.0] * 2 for i in range(n + 1)]
	s = [1]
	vis = [0] * (n + 1)
	done = [0] * (n + 1)
	while s:
		c = s[-1]
		if not vis[c]:
			vis[c] = 1
			for ne in adj[c]:
				if not vis[ne]:
					s.append(ne)
		else:
			for ne in adj[c]:
				if done[ne]:
					dp[c][1] += max(dp[ne][0] + abs(a[c][1] - a[ne][0]), dp[ne][1] + abs(a[c][1] - a[ne][1]))
					dp[c][0] += max(dp[ne][0] + abs(a[c][0] - a[ne][0]), dp[ne][1] + abs(a[c][0] - a[ne][1]))
			done[c] = 1
			s.pop()
	print(int(max(dp[1])))


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ANSL = []
t = int(input())
for tests in range(t):
	n = int(input())
	L = [0] * n
	R = [0] * n
	for i in range(n):
		(l, r) = map(int, input().split())
		L[i] = l
		R[i] = r
	E = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		E[x].append(y)
		E[y].append(x)
	ROOT = 0
	QUE = [ROOT]
	Parent = [-1] * (n + 1)
	Parent[ROOT] = n
	TOP_SORT = []
	while QUE:
		x = QUE.pop()
		TOP_SORT.append(x)
		for to in E[x]:
			if Parent[to] == -1:
				Parent[to] = x
				QUE.append(to)
	DPL = [0.0] * n
	DPR = [0.0] * n
	for x in TOP_SORT[1:][::-1]:
		p = Parent[x]
		DPL[p] += max(DPL[x] + abs(L[p] - L[x]), DPR[x] + abs(L[p] - R[x]))
		DPR[p] += max(DPL[x] + abs(R[p] - L[x]), DPR[x] + abs(R[p] - R[x]))
	ANSL.append(str(int(max(DPL[0], DPR[0]))))
sys.stdout.write('\n'.join(ANSL))


import sys
input = sys.stdin.readline

def dfs(u, p, d, dp0, dp1, l, r):
	for neighbor in d[u]:
		if neighbor != p:
			dfs(neighbor, u, d, dp0, dp1, l, r)
	dp0[p] += max(dp0[u] + abs(l[p] - l[u]), dp1[u] + abs(l[p] - r[u]))
	dp1[p] += max(dp0[u] + abs(r[p] - l[u]), dp1[u] + abs(r[p] - r[u]))

def solve():
	n = int(input())
	(l, r, dp0, dp1) = ([0] * (n + 1), [0] * (n + 1), [0] * (n + 1), [0] * (n + 1))
	for i in range(n):
		(x, y) = map(int, input().split())
		l[i + 1] = x
		r[i + 1] = y
	d = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	dfs(1, 0, d, dp0, dp1, l, r)
	print(max(dp0[1], dp1[1]))
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline

def dfs(i, p, l0, l1, dp0, dp1, adj):
	for j in adj[i]:
		if j != p:
			dfs(j, i, l0, l1, dp0, dp1, adj)
	dp0[p] += max(dp0[i] + abs(l0[p] - l0[i]), dp1[i] + abs(l0[p] - l1[i]))
	dp1[p] += max(dp0[i] + abs(l1[p] - l0[i]), dp1[i] + abs(l1[p] - l1[i]))

def solve():
	n = int(input())
	(l0, l1) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(1, n + 1):
		(l0[i], l1[i]) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	(dp1, dp0) = ([0] * (n + 1), [0] * (n + 1))
	dfs(1, 0, l0, l1, dp0, dp1, adj)
	print(max(dp0[1], dp1[1]))
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline

def dfs(u, p, adj, dp0, dp1, lr0, lr1):
	for v in adj[u]:
		if v != p:
			dfs(v, u, adj, dp0, dp1, lr0, lr1)
	dp0[p] += max(dp0[u] + abs(lr0[p] - lr0[u]), dp1[u] + abs(lr0[p] - lr1[u]))
	dp1[p] += max(dp0[u] + abs(lr1[p] - lr0[u]), dp1[u] + abs(lr1[p] - lr1[u]))

def solve():
	n = int(input())
	lr0 = [0] * (n + 1)
	lr1 = [0] * (n + 1)
	dp0 = [0] * (n + 1)
	dp1 = [0] * (n + 1)
	for i in range(1, n + 1):
		(lr0[i], lr1[i]) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	dfs(1, 0, adj, dp0, dp1, lr0, lr1)
	print(max(dp0[1], dp1[1]))
for _ in range(int(input())):
	solve()


import sys, io, os
try:
	Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(int, Z().split())
O = []
for _ in range(int(Z())):
	n = int(Z())
	w = [tuple(Y()) for i in range(n)]
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = Y()
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	d = [[0, 0] for i in range(n)]
	q = [(0, 0, -1)]
	while len(q):
		(t, v, p) = q[-1]
		del q[-1]
		if t:
			for i in g[v]:
				if i != p:
					for j in range(2):
						m = 0
						for k in range(2):
							m = max(m, abs(w[v][j] - w[i][k]) + d[i][k])
						d[v][j] += m
			continue
		q.append((1, v, p))
		for i in g[v]:
			if i != p:
				q.append((0, i, v))
	O.append(str(max(d[0])))
print('\n'.join(O))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	T = int(input())
	t = 1
	while t <= T:
		n = int(input())
		neigh = [[] for i in range(n)]
		smallest = [0] * n
		largest = [0] * n
		dp0 = [-1] * n
		dp1 = [-1] * n
		visited = [0] * n
		dic = {}
		for i in range(n):
			(s, l) = map(int, input().split())
			smallest[i] = s
			largest[i] = l
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			neigh[u - 1].append(v - 1)
			neigh[v - 1].append(u - 1)
		stack = []
		stack.append(0)
		visited[0] = 1
		seq = [0]
		while stack:
			index = stack.pop()
			for ele in neigh[index]:
				if visited[ele] == 1:
					continue
				visited[ele] = 1
				stack.append(ele)
				seq.append(ele)
		seq.reverse()
		for index in seq:
			dp0[index] = 0
			dp1[index] = 0
			inum0 = smallest[index]
			inum1 = largest[index]
			for e in neigh[index]:
				if dp0[e] == -1 or dp1[e] == -1:
					continue
				num00 = abs(inum0 - smallest[e]) + dp0[e]
				num01 = abs(inum0 - largest[e]) + dp1[e]
				num10 = abs(inum1 - smallest[e]) + dp0[e]
				num11 = abs(inum1 - largest[e]) + dp1[e]
				dp0[index] += max(num00, num01)
				dp1[index] += max(num10, num11)
		ans = max(dp0[0], dp1[0])
		print(ans)
		t += 1
main()


import sys
input = sys.stdin.buffer.readline
for t in range(int(input())):
	N = int(input())
	X = [list(map(int, input().split())) for i in range(N)]
	G = [[] for i in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		G[a].append(b)
		G[b].append(a)
	r = 0
	DP = [[0, 0] for i in range(N)]
	Q = [(r, 0, -1)]
	while len(Q):
		w = Q[-1]
		v = w[0]
		del Q[-1]
		if w[1]:
			for t in range(2):
				for i in range(len(G[v])):
					if w[2] == G[v][i]:
						continue
					m = 0
					for j in range(2):
						m = max(m, DP[G[v][i]][j] + abs(X[G[v][i]][j] - X[v][t]))
					DP[v][t] += m
			continue
		Q.append((v, 1, w[2]))
		for i in range(len(G[v])):
			if w[2] != G[v][i]:
				Q.append((G[v][i], 0, v))
	print(max(DP[0]))


import sys
input = sys.stdin.readline

def dfs(u, p, dp0, dp1, adj, lB, rB):
	for v in adj[u]:
		if v != p:
			dfs(v, u, dp0, dp1, adj, lB, rB)
	dp0[p] += max(dp0[u] + abs(lB[p] - lB[u]), dp1[u] + abs(lB[p] - rB[u]))
	dp1[p] += max(dp0[u] + abs(rB[p] - lB[u]), dp1[u] + abs(rB[p] - rB[u]))

def solve():
	n = int(input())
	lB = [0 for x in range(n + 1)]
	rB = [0 for x in range(n + 1)]
	dp0 = [0 for x in range(n + 1)]
	dp1 = [0 for x in range(n + 1)]
	for i in range(1, n + 1):
		(lB[i], rB[i]) = map(int, input().split())
	adj = [[] for x in range(n + 1)]
	for k in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	dfs(1, 0, dp0, dp1, adj, lB, rB)
	print(max(dp0[1], dp1[1]))
for _ in range(int(input())):
	solve()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
mm = (1 << 30) - 1
T = int(input())
for _ in range(T):
	N = int(input())
	LR = [0] * N
	for i in range(N):
		(l, r) = map(int, input().split())
		LR[i] = (l << 30) + r
	X = [[] for i in range(N)]
	for i in range(N - 1):
		(x, y) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		X[x].append(y)
		X[y].append(x)
	P = [-1] * N
	Q = deque([0])
	R = []
	while Q:
		i = deque.popleft(Q)
		R.append(i)
		for a in X[i]:
			if a != P[i]:
				P[a] = i
				X[a].remove(i)
				deque.append(Q, a)
	LL = [0.0] * N
	RR = [0.0] * N
	for i in R[1:][::-1]:
		p = P[i]
		lr = LR[i]
		(l, r) = (lr >> 30, lr & mm)
		lr = LR[p]
		(ll, rr) = (lr >> 30, lr & mm)
		LL[p] += max(abs(l - ll) + LL[i], abs(r - ll) + RR[i])
		RR[p] += max(abs(l - rr) + LL[i], abs(r - rr) + RR[i])
	print(int(max(LL[0], RR[0]) + 0.5))


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
for _ in range(int(input())):
	N = int(input())
	A = [list(map(int, input().split())) for _ in range(N)]
	G = [[] for _ in range(N)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		G[u].append(v)
		G[v].append(u)
	ans = [-1] * (2 * N)

	@bootstrap
	def dfs(u, p, i):
		if ans[2 * u + i] == -1:
			a = A[u][i]
			best = 0.0
			for v in G[u]:
				if v != p:
					yield dfs(v, u, 0)
					yield dfs(v, u, 1)
					best += max(abs(a - A[v][0]) + ans[2 * v], abs(a - A[v][1]) + ans[2 * v + 1])
			ans[2 * u + i] = best
		yield
	dfs(0, -1, 0)
	dfs(0, -1, 1)
	print(int(max(ans[0], ans[1])))


import sys
import getpass
from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = False

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve_(minrr, maxrr, edges):
	g = {i: [] for i in range(len(minrr))}
	for (a, b) in edges:
		g[a - 1].append(b - 1)
		g[b - 1].append(a - 1)
	entered = set([0])
	exiting = set()
	prev = [-1] * len(minrr)
	resmincur = [0] * len(minrr)
	resmaxcur = [0] * len(minrr)

	def operate(cur, nex):
		if cur == -1:
			return
		resminnex = resmincur[nex]
		resmaxnex = resmaxcur[nex]
		resmax = max(resminnex + abs(minrr[nex] - maxrr[cur]), resmaxnex + abs(maxrr[nex] - maxrr[cur]))
		resmin = max(resmaxnex + abs(maxrr[nex] - minrr[cur]), resminnex + abs(minrr[nex] - minrr[cur]))
		resmincur[cur] += resmin
		resmaxcur[cur] += resmax
	stack = [0]
	while stack:
		cur = stack[-1]
		if cur in exiting:
			stack.pop()
			operate(prev[cur], cur)
			continue
		for nex in g[cur]:
			if nex in entered:
				continue
			entered.add(nex)
			stack.append(nex)
			prev[nex] = cur
		exiting.add(cur)
	return int(max(resmincur[0], resmaxcur[0]))
for case_num in range(int(input())):
	k = int(input())
	arr = [0] * k
	brr = [0] * k
	for i in range(k):
		(arr[i], brr[i]) = list(map(float, input().split()))
	edges = read_matrix(k - 1)
	res = solve(arr, brr, edges)
	print(res)


import sys, io, os
try:
	Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(int, Z().split())
O = []
for _ in range(int(Z())):
	n = int(Z())
	wl = []
	wr = []
	g = [[] for i in range(n)]
	for i in range(n):
		(x, y) = Y()
		wl.append(x)
		wr.append(y)
	for i in range(n - 1):
		(u, v) = Y()
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	l = [0.0] * n
	r = [0.0] * n
	c = [-1] * n
	p = [-1] * n
	q = [0]
	while q:
		v = q.pop()
		if c[v] == -1:
			c[v] = 0
			for i in g[v]:
				if i != p[v]:
					p[i] = v
					c[v] += 1
					q.append(i)
		if c[v] == 0:
			for i in g[v]:
				if i != p[v]:
					l[v] += max(abs(wl[v] - wl[i]) + l[i], abs(wl[v] - wr[i]) + r[i])
					r[v] += max(abs(wr[v] - wl[i]) + l[i], abs(wr[v] - wr[i]) + r[i])
			c[p[v]] -= 1
			if v and c[p[v]] == 0:
				q.append(p[v])
	O.append(str(int(max(l[0], r[0]))))
print('\n'.join(O))


import sys
input = sys.stdin.readline

def dfs(ls, vs, dp_l, dp_v, adj, node, parent):
	for child in adj[node]:
		if child != parent:
			dfs(ls, vs, dp_l, dp_v, adj, child, node)
	dp_l[parent] += max(dp_l[node] + abs(ls[parent] - ls[node]), dp_v[node] + abs(ls[parent] - vs[node]))
	dp_v[parent] += max(dp_l[node] + abs(vs[parent] - ls[node]), dp_v[node] + abs(vs[parent] - vs[node]))
	pass

def solve():
	n = int(input())
	ls = [0] * (n + 1)
	vs = [0] * (n + 1)
	dp_l = [0] * (n + 1)
	dp_v = [0] * (n + 1)
	for i in range(1, n + 1):
		(ls[i], vs[i]) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(1, n):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	dfs(ls, vs, dp_l, dp_v, adj, 1, 0)
	print(max(dp_l[1], dp_v[1]))
	pass
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.buffer.readline

def main():
	t = int(input())
	INF = float('inf')
	for _ in range(t):
		n = int(input())
		L = []
		R = []
		for i in range(n):
			(l, r) = map(int, input().split())
			L.append(l)
			R.append(r)
		G = [[] for _ in range(n)]
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			G[a].append(b)
			G[b].append(a)
		root = 0
		par = [-1] * n
		stack = []
		stack.append(~0)
		stack.append(0)
		dp = [[0, 0] for _ in range(n)]
		while stack:
			v = stack.pop()
			if v >= 0:
				for u in G[v]:
					if u == par[v]:
						continue
					par[u] = v
					stack.append(~u)
					stack.append(u)
			else:
				u = ~v
				v = par[u]
				if v == -1:
					continue
				zero = max(dp[u][0] + abs(L[v] - L[u]), dp[u][1] + abs(L[v] - R[u]))
				one = max(dp[u][0] + abs(R[v] - L[u]), dp[u][1] + abs(R[v] - R[u]))
				dp[v][0] += zero
				dp[v][1] += one
		ans = max(dp[0])
		print(ans)
main()