Geek has developed an effective vaccine for Corona virus and he wants each of the N houses in Geek Land to have access to it. Given a binary tree where each node represents a house in Geek Land, find the minimum number of houses that should be supplied with the vaccine kit if one vaccine kit is sufficient for that house, its parent house and it's immediate child nodes.  
 
Example 1:
Input:
    1
   / \
  2   3 
        \
         4
          \
           5
            \
             6
Output:
2
Explanation:
The vaccine kits should be 
supplied to house numbers 1 and 5. 
Example 2:
Input:
    1
   / \
  2   3 
Output:
1
Explanation:
The vaccine kits should be 
supplied to house number 1.
Your Task:
You don't need to read input or print anything. Complete the function supplyVaccine() which takes the root of the housing tree as input parameter and returns the minimum number of houses that should be supplied with the vaccine kit.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

        '''

class Solution:

    def supplyVaccine(self, root):

        # Your code goes here



Solutions:
class Solution:
	number = 0

	def rec_count_vaccine(self, root):
		if root is None:
			return (True, False)
		(L_got_vac, L_own_vac) = self.rec_count_vaccine(root.left)
		(R_got_vac, R_own_vac) = self.rec_count_vaccine(root.right)
		root_got_vac = False
		root_own_vac = False
		if L_own_vac or R_own_vac:
			root_got_vac = True
		if L_got_vac == False or R_got_vac == False:
			root_own_vac = True
			root_got_vac = True
			self.number += 1
		return (root_got_vac, root_own_vac)

	def supplyVaccine(self, root):
		(got_vac, own_vac) = self.rec_count_vaccine(root)
		if got_vac == False:
			self.number += 1
		return self.number


class Solution:

	def solve(self, p):
		if not p:
			return 0
		left = self.solve(p.left)
		right = self.solve(p.right)
		if left == 1 or right == 1:
			self.ans += 1
			return 2
		if left == 2 or right == 2:
			return 0
		return 1

	def supplyVaccine(self, root):
		self.ans = 0
		if self.solve(root) == 1:
			self.ans += 1
		return self.ans


class Solution:
	v = 0

	def solve(self, node):
		if node == None:
			return 0
		l = self.solve(node.left)
		r = self.solve(node.right)
		if l == 1 or r == 1:
			self.v += 1
		if l == 0:
			return r % 3 + 1
		if r == 0:
			return l % 3 + 1
		return min(l, r) % 3 + 1

	def supplyVaccine(self, root):
		m = self.solve(root)
		if m == 1:
			self.v += 1
		return self.v


class Solution:
	vaccine = 0

	def checkVacc(self, root):
		if not root:
			return
		left = self.checkVacc(root.left)
		right = self.checkVacc(root.right)
		if right is 'want' or left is 'want':
			self.vaccine += 1
			return 'gave'
		if right is 'gave' or left is 'gave':
			return 'Ok'
		return 'want'

	def supplyVaccine(self, root):
		if self.checkVacc(root) is 'want':
			self.vaccine += 1
		return self.vaccine


novaccine = 0

class Solution:

	def supplyVaccine(self, root):
		if self.vaccine(root) == 'want':
			global novaccine
			novaccine += 1
		ans = novaccine
		novaccine = 0
		return ans

	def vaccine(self, root):
		if not root:
			return 'ok'
		left = self.vaccine(root.left)
		right = self.vaccine(root.right)
		if left == 'want' or right == 'want':
			global novaccine
			novaccine += 1
			return 'provide'
		elif left == 'provide' or right == 'provide':
			return 'ok'
		return 'want'


class Solution:

	def traverse(self, n):
		if not n:
			return (0, 2)
		(vaccineKitL, distL) = self.traverse(n.left)
		(vaccineKitR, distR) = self.traverse(n.right)
		if max(distL, distR) == 3:
			return (vaccineKitL + vaccineKitR + 1, 1)
		return (vaccineKitL + vaccineKitR, 1 + min(distL, distR))

	def supplyVaccine(self, root):
		(vaccine_kits, distance) = self.traverse(root)
		if distance == 3:
			return vaccine_kits + 1
		return vaccine_kits


class Solution:

	def supplyVaccine(self, root):
		ans = [0]

		def rec(nod):
			if nod is None:
				return 2
			lef = rec(nod.left)
			righ = rec(nod.right)
			if lef == 0 or righ == 0:
				ans[0] += 1
				return 1
			elif lef == 2 and righ == 2:
				return 0
			return 2
		if rec(root) == 0:
			ans[0] += 1
		return ans[0]


class Solution:
	vaccine = 0

	def countvaccine(self, root):
		if root is None:
			return
		left = self.countvaccine(root.left)
		right = self.countvaccine(root.right)
		if left == 'want' or right == 'want':
			self.vaccine += 1
			return 'provide'
		if left == 'provide' or right == 'provide':
			return 'ok'
		return 'want'

	def supplyVaccine(self, root):
		if self.countvaccine(root) == 'want':
			self.vaccine += 1
		return self.vaccine


is_fed = {None: False}

def check_fed(node):
	if node in is_fed.keys():
		return True
	return False

def feed(gp, root, cnt):
	if root is None:
		return cnt
	cnt = feed(root, root.left, cnt)
	cnt = feed(root, root.right, cnt)
	if root.left is not None and (not check_fed(root.left)) or (root.right is not None and (not check_fed(root.right))):
		is_fed[gp] = True
		is_fed[root] = True
		is_fed[root.right] = True
		is_fed[root.left] = True
		return cnt + 1
	return cnt

class Solution:

	def supplyVaccine(self, root):
		is_fed.clear()
		cnt = feed(None, root, 0)
		if not check_fed(root):
			return cnt + 1
		return cnt


class Solution:

	def supplyVaccine(self, root):

		def traverse(head, root, ans):
			if not root:
				return 0
			l = traverse(head, root.left, ans)
			r = traverse(head, root.right, ans)
			if root == head:
				if max(l, r) == -1 and min(l, r) == -1:
					return 0
				elif max(l, r) == 0 and min(l, r) == -1:
					return 0
				else:
					ans[0] += 1
					return 0
			if max(l, r) + 1 == 2:
				ans[0] += 1
				return -1
			elif max(l, r) == 0 and min(l, r) == -1:
				return 0
			else:
				return max(l, r) + 1
		ans = [0]
		traverse(root, root, ans)
		return ans[0]


class Solution:

	def supplyVaccine(self, root):
		res = [0]

		def solve(root, res):
			if root == None:
				return 2
			left = solve(root.left, res)
			right = solve(root.right, res)
			if left == 0 or right == 0:
				res[0] += 1
				return 1
			if left == 2 and right == 2:
				return 0
			return 2
		k = solve(root, res)
		if k == 0:
			return res[0] + 1
		return res[0]


class Solution:

	def supplyVaccine(self, root):
		ans = [0]
		if self.recursion(root, ans) == 0:
			ans[0] += 1
		return ans[0]

	def recursion(self, root, ans):
		if root is None:
			return 1
		left = self.recursion(root.left, ans)
		right = self.recursion(root.right, ans)
		if left == 0 or right == 0:
			ans[0] += 1
			return 2
		elif left == 2 or right == 2:
			return 1
		else:
			return 0


class Solution:
	vaccine = 0

	def countvaccine(self, root):
		if root == None:
			return
		left = self.countvaccine(root.left)
		right = self.countvaccine(root.right)
		if left == 'want' or right == 'want':
			self.vaccine += 1
			return 'provide'
		if left == 'provide' or right == 'provide':
			return 'ok'
		return 'want'

	def supplyVaccine(self, root):
		if self.countvaccine(root) == 'want':
			self.vaccine += 1
		return self.vaccine
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		ob = Solution()
		print(ob.supplyVaccine(root))


class Solution:

	def traverse(self, root, count):
		if root == None:
			return 1
		l = self.traverse(root.left, count)
		r = self.traverse(root.right, count)
		if l == -1 or r == -1:
			count[0] += 1
			return 0
		if l == 0 or r == 0:
			return 1
		return -1

	def supplyVaccine(self, root):
		count = [0]
		if self.traverse(root, count) == -1:
			count[0] += 1
		return count[0]


NEED_VACCINE = 0
HAS_VACCINE = 1
NO_NEED_OF_VACCINE = 2

class Solution:

	def supplyVaccine(self, root):
		vaccineCount = [0]
		if self._supplyVaccine(root, vaccineCount) == NEED_VACCINE:
			vaccineCount[0] += 1
		return vaccineCount[0]

	def _supplyVaccine(self, root, vaccineCount):
		if not root:
			return NO_NEED_OF_VACCINE
		left = self._supplyVaccine(root.left, vaccineCount)
		right = self._supplyVaccine(root.right, vaccineCount)
		if left == NEED_VACCINE or right == NEED_VACCINE:
			vaccineCount[0] += 1
			return HAS_VACCINE
		elif left == HAS_VACCINE or right == HAS_VACCINE:
			return NO_NEED_OF_VACCINE
		else:
			return NEED_VACCINE


class Solution:
	vaccine = 0

	def countVaccine(self, root):
		if not root:
			return 'ok'
		left = self.countVaccine(root.left)
		right = self.countVaccine(root.right)
		if left == 'want' or right == 'want':
			self.vaccine += 1
			return 'provide'
		if left == 'provide' or right == 'provide':
			return 'ok'
		return 'want'

	def supplyVaccine(self, root):
		if self.countVaccine(root) == 'want':
			self.vaccine += 1
		return self.vaccine


class Solution:

	def supplyVaccine(self, root):

		def dfs(node):
			if not node:
				return 1
			l = dfs(node.left)
			r = dfs(node.right)
			if l == 0 or r == 0:
				self.sum += 1
				return 2
			elif l == 2 or r == 2:
				return 1
			else:
				return 0
		self.sum = 0
		if dfs(root) == 0:
			self.sum += 1
		return self.sum


class Solution:

	def supplyVaccine(self, root):

		def dfs(root):
			if root is None:
				return -1
			left_status = dfs(root.left)
			right_status = dfs(root.right)
			if left_status == 0 or right_status == 0:
				self.vaccine += 1
				return 1
			elif left_status == 1 or right_status == 1:
				return 2
			return 0
		self.vaccine = 0
		if dfs(root) == 0:
			self.vaccine += 1
		return self.vaccine


class Solution:

	def supplyVaccine(self, root):
		(c, d) = self.count_dist(root)
		return c + d // 2

	def count_dist(self, node):
		if not node.left and (not node.right):
			return (0, 2)
		(lc, ld) = self.count_dist(node.left) if node.left else (0, 3)
		(rc, rd) = self.count_dist(node.right) if node.right else (0, 3)
		c = lc + rc
		if ld == 2 or rd == 2:
			c += 1
			d = 0
		else:
			d = min(ld, rd) + 1
		return (c, d)


class Solution:
	totalVaccine = 0

	def supplyVaccine(self, root):

		def confirmation(root):
			if root == None:
				return 'protected'
			leftWant = confirmation(root.left)
			rightWant = confirmation(root.right)
			if leftWant == 'want' or rightWant == 'want':
				self.totalVaccine += 1
				return 'provider'
			elif leftWant == 'provider' or rightWant == 'provider':
				return 'protected'
			else:
				return 'want'
		if confirmation(root) == 'want':
			self.totalVaccine += 1
		return self.totalVaccine


class Solution:

	def need(self, root):
		global v
		if root == None:
			return 0
		left = self.need(root.left)
		right = self.need(root.right)
		if left == -1 or right == -1:
			v += 1
			return 1
		if left == 1 or right == 1:
			return 0
		return -1

	def supplyVaccine(self, root):
		global v
		v = 0
		x = self.need(root)
		if x == -1:
			v += 1
		return v


class Solution:

	def supplyVaccine(self, root):
		(a, b) = self.cnt(root)
		return a + b // 2

	def cnt(self, node):
		if not node.left and (not node.right):
			return (0, 2)
		(la, lb) = self.cnt(node.left) if node.left else (0, 3)
		(ra, rb) = self.cnt(node.right) if node.right else (0, 3)
		a = la + ra
		if lb == 2 or rb == 2:
			a += 1
			b = 0
		else:
			b = min(lb, rb) + 1
		return (a, b)


class Solution:
	v = 0

	def vaccine(n):
		if n == None:
			return 0
		l = Solution.vaccine(n.left)
		r = Solution.vaccine(n.right)
		if l == -1 or r == -1:
			Solution.v += 1
			return 1
		elif l == 1 or r == 1:
			return 0
		return -1

	def supplyVaccine(self, root):
		Solution.v = 0
		if Solution.vaccine(root) == -1:
			Solution.v += 1
		return Solution.v


class Solution:

	def supplyVaccine(self, root):
		self.count = 0

		def supply(par, root):
			if not root:
				return False
			if not root.left and (not root.right):
				return True
			if supply(root, root.left):
				root.data = 0
				self.count += 1
			flag = supply(root, root.right)
			if root.data != 0 and flag:
				root.data = 0
				self.count += 1
			if root.data != 0:
				if root.left and root.left.data == 0:
					return False
				if root.right and root.right.data == 0:
					return False
				if not par:
					self.count += 1
				return True
			return False
		supply(None, root)
		return self.count


class Solution:

	def __init__(self):
		self.vac_count = 0

	def rec_count(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return -1
		lc = self.rec_count(root.left)
		rc = self.rec_count(root.right)
		if lc == -1 or rc == -1:
			self.vac_count += 1
			return 1
		if lc == 0 and rc == 0:
			return -1
			return 1
		if lc == 1 or rc == 1:
			return 0

	def supplyVaccine(self, root):
		_ = self.rec_count(root)
		if _ == -1:
			return self.vac_count + 1
		return self.vac_count


ans = 0

def mgc(root):
	global ans
	if not root:
		return 1
	left = mgc(root.left)
	right = mgc(root.right)
	if left == 1 and right == 1:
		return 2
	elif left == 2 or right == 2:
		ans += 1
		return 3
	return 1

class Solution:

	def supplyVaccine(self, root):
		global ans
		ans = 0
		if mgc(root) == 2:
			ans += 1
		return ans


class Solution:

	def supplyVaccine(self, root):
		global nv
		nv = 0
		if self.vacc(root) == 1:
			nv += 1
		return nv

	def vacc(self, root):
		global nv
		(l, r) = (0, 0)
		if root is None:
			return 0
		l = self.vacc(root.left)
		r = self.vacc(root.right)
		if l == 1 or r == 1:
			nv += 1
			return 2
		elif l == 2 or r == 2:
			return 0
		else:
			return 1


class Solution:

	def util(self, root, ans):
		if root is None:
			return 'mnc'
		left = self.util(root.left, ans)
		right = self.util(root.right, ans)
		if left == 'nm' or right == 'nm':
			ans[0] += 1
			return 'mwc'
		if left == 'mnc' and right == 'mnc':
			return 'nm'
		return 'mnc'

	def supplyVaccine(self, root):
		ans = [0]
		z = self.util(root, ans)
		if z == 'nm':
			ans[0] += 1
		return ans[0]


class Solution:

	def supplyVaccine(self, root):
		(count, dist) = self.count_dist(root)
		return count + dist // 2

	def count_dist(self, node):
		if not node.left and (not node.right):
			return (0, 2)
		(l_count, l_dist) = self.count_dist(node.left) if node.left else (0, 3)
		(r_count, r_dist) = self.count_dist(node.right) if node.right else (0, 3)
		count = l_count + r_count
		if l_dist == 2 or r_dist == 2:
			count += 1
			dist = 0
		else:
			dist = min(l_dist, r_dist) + 1
		return (count, dist)


class Solution:

	def supplyVaccine(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		self.count = 0
		self.needs = 1
		self.covered = 2
		self.has_vaccine_kit = 3
		self.not_need = 4
		if self.needs == self.helper(root):
			self.count += 1
		return self.count

	def helper(self, root):
		if not root:
			return self.not_need
		if not root.left and (not root.right):
			return self.needs
		left = self.helper(root.left)
		right = self.helper(root.right)
		if left == self.needs or right == self.needs:
			self.count += 1
			return self.has_vaccine_kit
		if left == self.has_vaccine_kit or right == self.has_vaccine_kit:
			return self.covered
		return self.needs


class Solution:

	def __init__(self):
		self.no_vac = 0

	def vaccine(self, root):
		if root is None:
			return -1
		left = self.vaccine(root.left)
		right = self.vaccine(root.right)
		if left == 1 or right == 1:
			self.no_vac = self.no_vac + 1
			return 0
		elif left == 0 or right == 0:
			return -1
		else:
			return 1

	def supplyVaccine(self, root):
		if self.vaccine(root) == 1:
			self.no_vac += 1
		return self.no_vac


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def __init__(self):
		self.vaccine = 0

	def vaccine_needed(self, root):
		if root is None:
			return -1
		left = self.vaccine_needed(root.left)
		right = self.vaccine_needed(root.right)
		if left == 1 or right == 1:
			self.vaccine = self.vaccine + 1
			return 0
		if left == 0 or right == 0:
			return -1
		return 1

	def supplyVaccine(self, root):
		if self.vaccine_needed(root) == 1:
			self.vaccine = self.vaccine + 1
		return self.vaccine


class Solution:

	def supplyVaccine(self, root):
		cnt = []

		def solve(root):
			if root == None:
				return 1
			lChild = solve(root.left)
			rChild = solve(root.right)
			if lChild == -1 or rChild == -1:
				cnt.append(1)
				return 0
			if lChild == 0 or rChild == 0:
				return 1
			return -1
		if solve(root) == -1:
			cnt.append(1)
		return len(cnt)


class Solution:

	def res(self, root, c):
		if root is None:
			return 0
		l = self.res(root.left, c)
		r = self.res(root.right, c)
		if l == 0 and r == 1:
			return 0
		if l == 1 and r == 0:
			return 0
		if l == 0 and r == 0:
			return -1
		if l == 1 and r == 1:
			return 0
		if l == -1 or r == -1:
			c[0] += 1
			return 1

	def supplyVaccine(self, root):
		c = [0]
		l = self.res(root, c)
		if l == -1:
			c[0] += 1
		return c[0]


from collections import defaultdict

class Solution:

	def supplyVaccine(self, root):
		dct = defaultdict(lambda : 0)
		res = [0]

		def count(root, dct, res):
			if not root:
				return
			count(root.left, dct, res)
			count(root.right, dct, res)
			if dct[root.left] == -1 or dct[root.right] == -1:
				dct[root] = 1
				res[0] += 1
			elif dct[root.left] == 1 or dct[root.right] == 1:
				dct[root] = 0
			else:
				dct[root] = -1
		count(root, dct, res)
		if dct[root] == -1:
			res[0] += 1
		return res[0]


class Solution:

	def Vaccine(self, root):
		global cnt
		if root == None:
			return 1
		L = Solution().Vaccine(root.left)
		R = Solution().Vaccine(root.right)
		if L == 1 and R == 1:
			return 2
		elif L == 2 or R == 2:
			cnt += 1
			return 3
		return 1

	def supplyVaccine(self, root):
		global cnt
		cnt = 0
		value = Solution().Vaccine(root)
		return cnt + (1 if value == 2 else 0)


class Solution:

	def supplyVaccine(self, root):
		self.vaxKit = 0
		res = self.supplyVaccineRecursive(root)
		if res == -1:
			self.vaxKit += 1
		return self.vaxKit

	def supplyVaccineRecursive(self, root):
		if not (root.left or root.right):
			return -1
		else:
			right = 0
			left = 0
			if root.left:
				left = self.supplyVaccineRecursive(root.left)
			if root.right:
				right = self.supplyVaccineRecursive(root.right)
			if left == -1 or right == -1:
				self.vaxKit += 1
				return 1
			if left == 1 or right == 1:
				return 0
			if left == 0 and right == 0:
				return -1


class Solution:

	def supplyVaccine(self, root):
		cnt = [0]

		def solve(root):
			if not root:
				return 0
			left = solve(root.left)
			right = solve(root.right)
			if left == -1 or right == -1:
				cnt[0] += 1
				return 1
			if left == 1 or right == 1:
				return 0
			return -1
		if solve(root) == -1:
			cnt[0] += 1
		return cnt[0]


class Solution:

	def supplyVaccine(self, root):
		ans = 0

		def vaccineGame(root):
			nonlocal ans
			if root is None:
				return 0
			l = vaccineGame(root.left)
			r = vaccineGame(root.right)
			if l == -2 or r == -2:
				ans += 1
				return -1
			elif l == -1 or r == -1:
				return 0
			return -2
		val = vaccineGame(root)
		if val == -2:
			ans += 1
		return ans


class Solution:

	def helper(self, root, count):
		if root is None:
			return 0
		left = self.helper(root.left, count)
		right = self.helper(root.right, count)
		if left == -1 or right == -1:
			count[0] += 1
			return 1
		if left == 1 or right == 1:
			return 0
		return -1

	def supplyVaccine(self, root):
		count = [0]
		if self.helper(root, count) == -1:
			count[0] += 1
		return count[0]


class Solution:

	def supplyVaccine(self, root):
		global ans
		ans = 0
		if self.vaccine(root) == 'want':
			ans += 1
		return ans

	def vaccine(self, root):
		global ans
		if root == None:
			return 'ok'
		left = self.vaccine(root.left)
		right = self.vaccine(root.right)
		if left == 'want' or right == 'want':
			ans += 1
			return 'provide'
		if left == 'provide' or right == 'provide':
			return 'ok'
		return 'want'


class Solution:

	def _supplyVaccine(self, node, kit):
		if not node:
			return 0
		if not node.left and (not node.right):
			return -1
		kit_required_by_left = self._supplyVaccine(node.left, kit)
		kit_required_by_right = self._supplyVaccine(node.right, kit)
		if kit_required_by_left == -1 or kit_required_by_right == -1:
			kit[0] += 1
			return 1
		if kit_required_by_left == 1 or kit_required_by_right == 1:
			return 0
		return -1

	def supplyVaccine(self, root):
		try:
			kit = [0]
			if self._supplyVaccine(root, kit) == -1:
				kit[0] += 1
			return kit[0]
		except Exception as err:
			print(err)
			return 1


class Solution:
	noVaccine = 0

	def vaccine(self, root):
		if root == None:
			return 'OK'
		left = self.vaccine(root.left)
		right = self.vaccine(root.right)
		if left == 'WANT' or right == 'WANT':
			self.noVaccine += 1
			return 'PROVIDE'
		elif left == 'PROVIDE' or right == 'PROVIDE':
			return 'OK'
		return 'WANT'

	def supplyVaccine(self, root):
		if self.vaccine(root) == 'WANT':
			self.noVaccine += 1
		return self.noVaccine


global res

class Solution:

	def supplyVaccine(self, root):
		global res
		res = 0
		if root == None:
			return 0
		if dfs(root) == 0:
			return 1 + res
		else:
			return res

def dfs(root):
	if root == None:
		return 2
	lf = dfs(root.left)
	rr = dfs(root.right)
	if lf == 0 or rr == 0:
		global res
		res = res + 1
		return 1
	if lf == 1 or rr == 1:
		return 2
	else:
		return 0


class Solution:

	def supplyVaccine(self, root):
		self.req = 0

		def inspect(r):
			if r == None:
				return 0
			lc = inspect(r.left)
			rc = inspect(r.right)
			if lc == -1 or rc == -1:
				self.req += 1
				return 1
			elif lc == 1 or rc == 1:
				return 0
			return -1
		v = inspect(root)
		return self.req if v != -1 else self.req + 1


class Solution:

	def supplyVaccine(self, root):

		def dfs(node):
			if not node:
				return (float('inf'), 0, 0)
			(l_kit, l_covered, l_notcovered) = dfs(node.left)
			(r_kit, r_covered, r_notcovered) = dfs(node.right)
			kit = min(l_kit, l_covered, l_notcovered) + min(r_kit, r_covered, r_notcovered) + 1
			covered = min(min(l_kit, l_covered) + r_kit, min(r_kit, r_covered) + l_kit)
			notcovered = l_covered + r_covered
			return (kit, covered, notcovered)
		(k, c, nc) = dfs(root)
		return min(k, c, nc + 1)


class Solution:
	vaccine = 0

	def need_vaccine(self, root):
		if root is None:
			return (True, False)
		(left_got, left_own) = self.need_vaccine(root.left)
		(right_got, right_own) = self.need_vaccine(root.right)
		root_got = False
		root_own = False
		if left_own or right_own:
			root_got = True
		if left_got == False or right_got == False:
			root_own = True
			root_got = True
			self.vaccine += 1
		return (root_got, root_own)

	def supplyVaccine(self, root):
		(got_vac, _) = self.need_vaccine(root)
		if got_vac == False:
			self.vaccine += 1
		return self.vaccine


class Solution:

	def supplyVaccine(self, root):
		self.ans = 0
		parentNeeds = self.travel(root)
		if parentNeeds == -1:
			self.ans += 1
		return self.ans

	def travel(self, node):
		if not node:
			return 1
		lc = self.travel(node.left)
		rc = self.travel(node.right)
		if lc == -1 or rc == -1:
			self.ans += 1
			return 0
		if lc == 0 or rc == 0:
			return 1
		return -1


class Solution:

	def supplyVaccine(self, root):
		self.ans = 0
		covered = {None}

		def dfs(node, par=None):
			if node:
				dfs(node.left, node)
				dfs(node.right, node)
				if par is None and node not in covered or node.left not in covered or node.right not in covered:
					self.ans += 1
					covered.update({node, par, node.left, node.right})
		dfs(root)
		return self.ans


class Solution:
	provider = 0

	def supply(self, root):
		if not root:
			return 0
		l = self.supply(root.left)
		r = self.supply(root.right)
		if l == -1 or r == -1:
			self.provider += 1
			return 1
		elif l == 1 or r == 1:
			return 0
		return -1

	def supplyVaccine(self, root):
		if self.supply(root) == -1:
			self.provider += 1
		return self.provider


class Node:

	def _init_(self, val):
		self.data = val
		self.left = None
		self.right = None

class Solution:
	v = 0

	def solve(self, node):
		if node == None:
			return 0
		l = self.solve(node.left)
		r = self.solve(node.right)
		if l == 1 or r == 1:
			self.v += 1
		if l == 0:
			return r % 3 + 1
		if r == 0:
			return l % 3 + 1
		return min(l, r) % 3 + 1

	def supplyVaccine(self, root):
		m = self.solve(root)
		if m == 1:
			self.v += 1
		return self.v


class Solution:

	def solve(self, root, count):
		if root == None:
			return 1
		l = self.solve(root.left, count)
		r = self.solve(root.right, count)
		if l == 1 and r == 1:
			return 2
		if l == 2 or r == 2:
			count[0] += 1
			return 3
		return 1

	def supplyVaccine(self, root):
		count = [0]
		if self.solve(root, count) == 2:
			count[0] += 1
		return count[0]


class Solution:
	vaccines = 0

	def getVaccines(self, root):
		if not root:
			return 1
		l = self.getVaccines(root.left)
		r = self.getVaccines(root.right)
		if l == -1 or r == -1:
			self.vaccines += 1
			return 0
		if l == 0 or r == 0:
			return 1
		return -1

	def supplyVaccine(self, root):
		if self.getVaccines(root) == -1:
			self.vaccines += 1
		return self.vaccines


class Solution:

	def supplyVaccine(self, root):
		v = 0

		def solve(node):
			nonlocal v
			if not node:
				return 0
			l = solve(node.left)
			r = solve(node.right)
			if l == 1 or r == 1:
				v += 1
			if l == 0:
				return r % 3 + 1
			if r == 0:
				return l % 3 + 1
			return min(l, r) % 3 + 1
		m = solve(root)
		return v if m != 1 else v + 1


class Solution:

	def find(self, root):
		if root is None:
			return -1
		left = self.find(root.left)
		right = self.find(root.right)
		if left == 1 or right == 1:
			self.vaccines += 1
			return 0
		if left == 0 or right == 0:
			return -1
		return 1

	def supplyVaccine(self, root):
		self.vaccines = 0
		if self.find(root) == 1:
			self.vaccines += 1
		return self.vaccines