Arun has a rooted tree of N vertices rooted at vertex 1. Each vertex can either be coloured black or white.

Initially, the vertices are coloured A_{1}, A_{2}, \ldots A_{N}, where A_{i} \in \{0, 1\} denotes the colour of the i-th vertex (here 0 represents white and 1 represents black). He wants to perform some operations to change the colouring of the vertices to B_{1}, B_{2}, \ldots B_{N} respectively.

Arun can perform the following operation any number of times. In one operation, he can choose any subtree and either paint all its vertices white or all its vertices black.

Help Arun find the minimum number of operations required to change the colouring of the vertices to B_{1}, B_{2}, \ldots B_{N} respectively.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the tree.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the initial colouring of the vertices of the tree.
- The third line of each test case contains N space-separated integers B_{1}, B_{2}, \dots, B_{N} denoting the final desired colouring of the vertices of the tree.
- The next N-1 lines contain two space-separated integers u and v — denoting an undirected edge between nodes u and v.

It is guaranteed that the edges given in the input form a tree.

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

For each testcase, output the minimum number of operations required to obtain the desired colouring.

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

$1 ≤ T ≤ 2 \cdot 10^{4}$
$1 ≤ N ≤ 3 \cdot 10^{5}$
$A_{i} \in \{0, 1\}$
$B_{i} \in \{0, 1\}$
$1 ≤ u, v ≤ N$ and $u \neq v$
- It is guaranteed that the edges given in the input form a tree.
- The sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$

----- Sample Input 1 ------ 
2
4
1 1 0 0
1 1 1 0
1 2
1 3
1 4
5
1 1 1 0 0
1 0 1 1 1
5 3
3 1
2 1
4 3
----- Sample Output 1 ------ 
1
2
----- explanation 1 ------ 
Test case $1$: Arun can choose the subtree rooted at $3$ and paint it black in one operation to achieve the desired colouring.

![sample1_{part1}]
$\rightarrow$
![sample1_{part2}]

Test case $2$: Consider the following sequence of operations.

![sample2_{part1}]

In the first operation, choose the subtree rooted at $3$ and paint it black.

![sample2_{part2}]

In the second operation, choose the subtree rooted at $2$ and paint it white.

![sample2_{part3}]

It can be shown that the desired colouring cannot be obtained in fewer operations.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Tree algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
from math import inf
from collections import defaultdict
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
t = int(input())

def solve():
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	B = [int(x) for x in input().split(' ')]
	d = defaultdict(list)
	for _ in range(N - 1):
		(x, y) = [int(x) for x in input().split(' ')]
		d[x].append(y)
		d[y].append(x)
	ans = 0

	@lru_cache(None)
	def go(node, parent, c, swapped):
		if len(d[node]) == 1 and node != 1:
			return 1 if swapped and c != B[node - 1] or (not swapped and A[node - 1] != B[node - 1]) else 0
		ans = inf
		if swapped:
			if c != B[node - 1]:
				tans = 1
				for child in d[node]:
					if child != parent:
						tans += go(child, node, B[node - 1], True)
				if tans < ans:
					ans = tans
			else:
				tans = 0
				for child in d[node]:
					if child != parent:
						tans += go(child, node, B[node - 1], True)
				if tans < ans:
					ans = tans
		else:
			if A[node - 1] == B[node - 1]:
				tans = 0
				for child in d[node]:
					if child != parent:
						tans += go(child, node, B[node - 1], False)
				if tans < ans:
					ans = tans
			tans = 1
			for child in d[node]:
				if child != parent:
					tans += go(child, node, B[node - 1], True)
			if tans < ans:
				ans = tans
		return ans
	print(go(1, None, A[0], False))
while t:
	solve()
	t -= 1


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(5 * 10 ** 5)
adj = []
arra = []
arrb = []
dp = []

def treeinput(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)
	return adj

def dfs(root, color, parent):
	if dp[root][color] != -1:
		return dp[root][color]
	ans = 0
	if color == -1:
		if arra[root] == arrb[root]:
			(res1, res2) = (0, 0)
			for node in adj[root]:
				if node != parent:
					res1 += dfs(node, arrb[root], root)
					res2 += dfs(node, -1, root)
			ans = min(res1 + 1, res2)
		else:
			for node in adj[root]:
				if node != parent:
					ans += dfs(node, arrb[root], root)
			ans += 1
	elif color == arrb[root]:
		for node in adj[root]:
			if node != parent:
				ans += dfs(node, color, root)
	else:
		for node in adj[root]:
			if node != parent:
				ans += dfs(node, arrb[root], root)
		ans += 1
	dp[root][color] = ans
	return ans
for _ in range(int(input())):
	n = int(input())
	arra = list(map(int, input().split()))
	arrb = list(map(int, input().split()))
	arra = [-1] + arra
	arrb = [-1] + arrb
	dp = [[-1, -1, -1] for i in range(n + 1)]
	adj = treeinput(n)
	print(dfs(1, -1, -1))


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

def dfs(p, prev, what):
	if dp[p][what] != -1:
		return dp[p][what]
	ans = 0
	if what == 2:
		if a[p - 1] == b[p - 1]:
			(x, y) = (0, 0)
			for i in child[p]:
				if i == prev:
					continue
				x += dfs(i, p, 2)
				y += dfs(i, p, b[p - 1])
			ans = min(x, y + 1)
		else:
			for i in child[p]:
				if i == prev:
					continue
				ans += dfs(i, p, b[p - 1])
			ans += 1
	elif what == b[p - 1]:
		for i in child[p]:
			if i == prev:
				continue
			ans += dfs(i, p, what)
	else:
		for i in child[p]:
			if i == prev:
				continue
			ans += dfs(i, p, b[p - 1])
		ans += 1
	dp[p][what] = ans
	return ans
for T in range(int(input())):
	n = int(input())
	a = inp()
	b = inp()
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = inp()
		child[u].append(v)
		child[v].append(u)
	dp = [[-1, -1, -1] for i in range(n + 1)]
	ans = dfs(1, -1, 2)
	print(ans)


import sys
import random
from collections import defaultdict

class DefaultDict:

	def __init__(self, default=None):
		self.default = default
		self.x = random.randrange(1, 1 << 31)
		self.dd = defaultdict(default)

	def __repr__(self):
		return '{' + ', '.join((f'{k ^ self.x}: {v}' for (k, v) in self.dd.items())) + '}'

	def __eq__(self, other):
		for k in set(self) | set(other):
			if self[k] != other[k]:
				return False
		return True

	def __or__(self, other):
		res = DefaultDict(self.default)
		for (k, v) in self.dd:
			res[k] = v
		for (k, v) in other.dd:
			res[k] = v
		return res

	def __len__(self):
		return len(self.dd)

	def __getitem__(self, item):
		return self.dd[item ^ self.x]

	def __setitem__(self, key, value):
		self.dd[key ^ self.x] = value

	def __delitem__(self, key):
		del self.dd[key ^ self.x]

	def __contains__(self, item):
		return item ^ self.x in self.dd

	def items(self):
		for (k, v) in self.dd.items():
			yield (k ^ self.x, v)

	def keys(self):
		for k in self.dd:
			yield (k ^ self.x)

	def values(self):
		for v in self.dd.values():
			yield v

	def __iter__(self):
		for k in self.dd:
			yield (k ^ self.x)

class Counter(DefaultDict):

	def __init__(self, aa=[]):
		super().__init__(int)
		for a in aa:
			self.dd[a ^ self.x] += 1

	def __add__(self, other):
		res = Counter()
		for k in set(self) | set(other):
			v = self[k] + other[k]
			if v > 0:
				res[k] = v
		return res

	def __sub__(self, other):
		res = Counter()
		for k in set(self) | set(other):
			v = self[k] - other[k]
			if v > 0:
				res[k] = v
		return res

	def __and__(self, other):
		res = Counter()
		for k in self:
			v = min(self[k], other[k])
			if v > 0:
				res[k] = v
		return res

	def __or__(self, other):
		res = Counter()
		for k in set(self) | set(other):
			v = max(self[k], other[k])
			if v > 0:
				res[k] = v
		return res

class Set:

	def __init__(self, aa=[]):
		self.x = random.randrange(1, 1 << 31)
		self.st = set()
		for a in aa:
			self.st.add(a ^ self.x)

	def __repr__(self):
		return '{' + ', '.join((str(k ^ self.x) for k in self.st)) + '}'

	def __len__(self):
		return len(self.st)

	def add(self, item):
		self.st.add(item ^ self.x)

	def discard(self, item):
		self.st.discard(item ^ self.x)

	def __contains__(self, item):
		return item ^ self.x in self.st

	def __iter__(self):
		for k in self.st:
			yield (k ^ self.x)

	def pop(self):
		return self.st.pop() ^ self.x

	def __or__(self, other):
		res = Set(self)
		for a in other:
			res.add(a)
		return res

	def __and__(self, other):
		res = Set()
		for a in self:
			if a in other:
				res.add(a)
		for a in other:
			if a in self:
				res.add(a)
		return res
sys.setrecursionlimit(300005)
int1 = lambda x: int(x) - 1
pDB = lambda *x: print(*x, end='\n', file=sys.stderr)
p2D = lambda x: print(*x, sep='\n', end='\n\n', file=sys.stderr)

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
inf = (1 << 63) - 1
md = 10 ** 9 + 7

def solve():
	n = II()
	aa = LI()
	bb = LI()
	to = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = LI1()
		to[u].append(v)
		to[v].append(u)
	if n == 1:
		print(1 - (aa[0] == bb[0]))
		return
	memo = {}

	def dfs(u, par, s):
		t = (u, par, s)
		if t in memo:
			return memo[t]
		res = 1
		for v in to[u]:
			if v == par:
				continue
			res += dfs(v, u, bb[u])
		if s == 2 and aa[u] == bb[u]:
			cur = 0
			for v in to[u]:
				if v == par:
					continue
				cur += dfs(v, u, 2)
			res = min(res, cur)
		if s == bb[u]:
			cur = 0
			for v in to[u]:
				if v == par:
					continue
				cur += dfs(v, u, s)
			res = min(res, cur)
		memo[t] = res
		return res
	ans = dfs(0, -1, 2)
	print(ans)
testnumber = II()
for testcase in range(testnumber):
	solve()