Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

In a *red-blue tree*, each vertex is either red or blue and adjacent vertices always have different colours.

You are given a tree with $N$ vertices (numbered $1$ through $N$). It is not necessarily a red-blue tree, but its vertices are still coloured red and blue. You may perform the following operation any number of times (including zero): choose two adjacent vertices and swap their colours.

Find the smallest number of operations required to transform the tree into a red-blue tree or determine that it is impossible.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N-1$ lines follow. Each of these lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.
The last line contains a string $S$ with length $N$. For each valid $i$, the $i$-th character of this string is either '0' if the $i$-th vertex is initially red or '1' if it is initially blue.

------  Output ------
Print a single line containing one integer ― the smallest number of operations or $-1$ if it is impossible to transform the tree into a red-blue tree.

------  Constraints ------
$1 ≤ T ≤ 100$  
$1 ≤ N ≤ 100,000$  
$1 ≤ u, v ≤ N$  
$S$ contains only characters '0' and '1'
the sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
1  

7  

1 2  

1 3  

2 4  

2 5  

3 6  

3 7  

0010010
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
Example case 1: We can perform the following operations:
- Swap the colours of vertices $1$ and $3$; the string of colours becomes "1000010".
- Swap the colours of vertices $1$ and $2$; the string of colours becomes "0100010".
- Swap the colours of vertices $6$ and $3$; the string of colours becomes "0110000", so the tree is a red-blue tree.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal


Solutions:
import sys
sys.setrecursionlimit(10 ** 6)

def calc_colors(nodes, x, colors, exp_color, parent):
	total_value = 0
	total_value1 = 0
	if exp_color == '1':
		val = 1
		next_exp = '0'
	else:
		val = -1
		next_exp = '1'
	if colors[x] != exp_color:
		total_value = val
	else:
		total_value1 = val
	total_dist = 0
	total_dist1 = 0
	for i in nodes[x]:
		if i == parent:
			continue
		(dist, val, dist1, val1) = calc_colors(nodes, i, colors, next_exp, x)
		total_dist += dist
		total_value += val
		total_dist1 += dist1
		total_value1 += val1
	total_dist += abs(total_value)
	total_dist1 += abs(total_value1)
	return (total_dist, total_value, total_dist1, total_value1)

def solve() -> None:
	n = int(input())
	nodes = []
	for i in range(n):
		nodes.append([])
	for i in range(n - 1):
		(u, v) = tuple(map(int, input().split()))
		nodes[u - 1].append(v - 1)
		nodes[v - 1].append(u - 1)
	colors = input()
	(dist1, val1, dist2, val2) = calc_colors(nodes, 0, colors, '0', 0)
	if val1 != 0 != val2:
		print(-1)
	elif val1 == 0 == val2:
		if dist1 > dist2:
			print(dist2)
		else:
			print(dist1)
	elif val1 == 0:
		print(dist1)
	else:
		print(dist2)
t = int(input())
for i in range(t):
	try:
		solve()
	except RecursionError:
		print('recursionerror')


import sys, math
import io, os
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
INF = float('inf')
mod = int(1000000000.0) + 7

def dfs(graph, start, col_start):
	n = len(graph)
	dp = [0] * n
	(visited, finished) = ([False] * n, [False] * n)
	ans = 0
	stack = [(start, col_start)]
	while stack:
		(start, c) = stack[-1]
		if not visited[start]:
			visited[start] = True
			for child in graph[start]:
				if not visited[child]:
					stack.append((child, 1 - c))
		else:
			stack.pop()
			if S[start] != c:
				dp[start] += S[start] - c
			for child in graph[start]:
				if finished[child]:
					dp[start] += dp[child]
					ans += abs(dp[child])
			finished[start] = True
	if dp[0] != 0:
		ans = -1
	return ans
for t in range(int(data())):
	n = int(data())
	graph = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = mdata()
		u -= 1
		v -= 1
		graph[u].append(v)
		graph[v].append(u)
	S = list(map(int, data()))
	ans1 = dfs(graph, 0, 0)
	ans2 = dfs(graph, 0, 1)
	if ans1 == -1 or ans2 == -1:
		out(max(ans1, ans2))
	else:
		out(min(ans1, ans2))


import sys
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	n = int(input())
	g = [[] for i in range(n)]
	visited = [False for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		g[a - 1].append(b - 1)
		g[b - 1].append(a - 1)
	col = [int(i) for i in str(input())]

	def dfs(node, k):
		cost = delta = 0
		visited[node] = True
		if col[node] != k:
			if k == 1:
				delta = 1
			else:
				delta = -1
		for i in g[node]:
			if visited[i] == False:
				(c, d) = dfs(i, k ^ 1)
				cost += c + abs(d)
				delta += d
		return (cost, delta)
	(cost1, delta1) = dfs(0, k=1)
	visited = [False for i in range(n)]
	(cost2, delta2) = dfs(0, k=0)
	if delta1 == 0:
		if delta2 == 0:
			print(min(cost1, cost2))
		else:
			print(cost1)
	elif delta2 == 0:
		print(cost2)
	else:
		print(-1)


import sys
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	N = int(input())
	G = [[] for i in range(N)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		G[u - 1] += [v - 1]
		G[v - 1] += [u - 1]
	C = [-1] * N
	C[0] = 0
	que = [0]
	g = [[] for i in range(N)]
	E = []
	while que:
		q = que.pop()
		c = 1 - C[q]
		for v in G[q]:
			if C[v] == -1:
				g[q] += [v]
				C[v] = c
		que += g[q]
		E += g[q]
	S = [int(i) for i in input()]
	sc = sum(C)
	ss = sum(S)
	if sc != ss and sc + ss != N:
		print(-1)
		continue
	if ss != sc:
		C = [1 - i for i in C]
	cs = [-1] * N
	ss = [-1] * N

	def countc(x, note, y):
		if note[x] != -1:
			return note[x]
		note[x] = y[x]
		for v in g[x]:
			note[x] += countc(v, note, y)
		return note[x]
	countc(0, cs, C)
	countc(0, ss, S)
	ans = 0
	for v in E:
		ans += abs(cs[v] - ss[v])
	if N % 2 == 0 and sc == N // 2:
		C = [1 - i for i in C]
		cs = [-1] * N
		countc(0, cs, C)
		ans = min(ans, sum([abs(cs[v] - ss[v]) for v in E]))
	print(ans)