fork download
copy 
  1. from sys import stdin
  2. g   = lambda : stdin.readline().strip()
  3. gl  = lambda : g().split()
  4. gil = lambda : [int(var) for var in gl()]
  5. gfl = lambda : [float(var) for var in gl()]
  6. gcl = lambda : list(g())
  7. gbs = lambda : [int(var) for var in g()]
  8. mod = int(1e9)+7
  9. inf = float("inf")
  10.  
  11. t, = gil()
  12. for _ in range(t):
  13. 	n, = gil()
  14. 	adj = [[] for _ in range(n+1)]
  15. 	isroot = [1]*(n+1)
  16. 	isroot[0] = 0
  17. 	for _ in range(n-1):
  18. 		x, y = gil()
  19. 		isroot[y] = 0
  20. 		adj[x].append(y)
  21.  
  22. 	clr = [-1]+gbs()
  23.  
  24. 	layers  = [[isroot.index(1)]]
  25.  
  26. 	while 1:
  27. 		temp = []
  28. 		for x in layers[-1]:
  29. 			for y in adj[x]:
  30. 				temp.append(y)
  31. 		if temp :
  32. 			layers.append(temp)
  33. 		else:
  34. 			break
  35.  
  36. 	l, b = 0, clr.count(1)
  37.  
  38. 	for i in range(len(layers)):
  39. 		if i&1:
  40. 			l+=len(layers[i])
  41.  
  42. 	# print(l, n-l, b, n-b)
  43.  
  44. 	if max(n-l, l) == max(n-b, b):
  45. 		currclr = 0 if l == b else 1
  46. 		rclr = [0]*(n+1)
  47. 		for l in layers :
  48. 			for x in l :
  49. 				rclr[x] = currclr
  50. 			currclr ^= 1
  51. 		# print(rclr)
  52.  
  53. 		reqTree, givenTree = [0]*(n+1), [0]*(n+1)
  54.  
  55. 		for l in reversed(layers):
  56. 			for x in l :
  57. 				for y in adj[x]:
  58.  
  59. 					# for given Tree
  60. 					givenTree[x] += clr[y] + givenTree[y]
  61.  
  62. 					# for required Tree 
  63. 					reqTree[x] += rclr[y] + reqTree[y]
  64.  
  65. 		# print(reqTree, "req")
  66. 		# print(givenTree, "given")
  67.  
  68. 		ans = 0
  69.  
  70. 		for x in range(1, n+1):
  71. 			for y in adj[x]:
  72. 				# x -- > y
  73. 				blr, blg = rclr[y] + reqTree[y], clr[y] + givenTree[y]
  74. 				ans += abs(blr-blg)
  75.  
  76. 		print(ans)
  77.  
  78.  
  79.  
  80.  
  81. 	else:
  82. 		print(-1)
  83.  
  84.  
  85.  
Runtime error #stdin #stdout #stderr 0.11s 23536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 11, in <module>
ValueError: not enough values to unpack (expected 1, got 0)
https://ideone.com/86IG4G
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!