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 = 1
  12. for _ in range(t):
  13. 	n, = gil()
  14. 	adj = [[] for _ in range(n+1)]
  15. 	clr = [-1]+[0]*(n)
  16. 	got = g()
  17. 	for i in range(n):
  18. 		if got[i] == "B":
  19. 			clr[i+1] = 1
  20.  
  21. 	isroot = [1]*(n+1)
  22. 	isroot[0] = 0
  23. 	for _ in range(n-1):
  24. 		x, y = gil()
  25. 		isroot[y] = 0
  26. 		adj[x].append(y)
  27.  
  28.  
  29. 	layers  = [[isroot.index(1)]]
  30.  
  31. 	while 1:
  32. 		temp = []
  33. 		for x in layers[-1]:
  34. 			for y in adj[x]:
  35. 				temp.append(y)
  36. 		if temp :
  37. 			layers.append(temp)
  38. 		else:
  39. 			break
  40.  
  41. 	l, b = 0, clr.count(1)
  42.  
  43. 	for i in range(len(layers)):
  44. 		if i&1:
  45. 			l+=len(layers[i])
  46.  
  47. 	# print(l, n-l, b, n-b)
  48.  
  49. 	if max(n-l, l) == max(n-b, b):
  50. 		currclr = 0 if l == b else 1
  51. 		rclr = [0]*(n+1)
  52. 		for l in layers :
  53. 			for x in l :
  54. 				rclr[x] = currclr
  55. 			currclr ^= 1
  56. 		# print(rclr)
  57.  
  58. 		reqTree, givenTree = [0]*(n+1), [0]*(n+1)
  59.  
  60. 		for l in reversed(layers):
  61. 			for x in l :
  62. 				for y in adj[x]:
  63.  
  64. 					# for given Tree
  65. 					givenTree[x] += clr[y] + givenTree[y]
  66.  
  67. 					# for required Tree 
  68. 					reqTree[x] += rclr[y] + reqTree[y]
  69.  
  70. 		# print(reqTree, "req")
  71. 		# print(givenTree, "given")
  72.  
  73. 		ans = 0
  74.  
  75. 		for x in range(1, n+1):
  76. 			for y in adj[x]:
  77. 				# x -- > y
  78. 				blr, blg = rclr[y] + reqTree[y], clr[y] + givenTree[y]
  79. 				ans += abs(blr-blg)
  80.  
  81. 		print(ans)
  82.  
  83.  
  84.  
  85.  
  86. 	else:
  87. 		print(-1)
  88.  
  89.  
  90.  
Runtime error #stdin #stdout #stderr 0.12s 23672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 13, in <module>
ValueError: not enough values to unpack (expected 1, got 0)
https://ideone.com/LCh1MT
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!