# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        prefixSum={0:1}
        self.pathSum=0
        self.counter=0

        def dfs(node):
            if not node:
                return

            self.pathSum+=node.val
            prefixSum[self.pathSum]=prefixSum.get(self.pathSum,0)+1
            if self.pathSum-sum in prefixSum:
                self.counter+=prefixSum[self.pathSum-sum]

            dfs(node.left)
            dfs(node.right)
            self.removefromMap(prefixSum,self.pathSum)
            self.pathSum-=node.val

        dfs(root)
        return self.counter

    def removefromMap(self,Map,val):
        if val not in Map:
            return
        if Map[val]==1:
            del Map[val]
        else:
            Map[val]-=1