/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    map<TreeNode*,TreeNode*> parent;
    unordered_map<TreeNode*,int> leaves;

    void parentMaker(TreeNode* root){

        if(root==nullptr){
            return;
        }

        if(root->left!=nullptr){
            parent[root->left]=root;

        }
        if(root->right!=nullptr){
            parent[root->right]=root;
        }

        parentMaker(root->left);
        parentMaker(root->right);
        return;
    }

    void leafMaker(TreeNode* root){

        if(root==nullptr){
            return;
        }

        if(root->left==nullptr&&root->right==nullptr){
            leaves[root]=1;
            return;
        }

        leafMaker(root->left);
        leafMaker(root->right);

        return;
    }

    map<TreeNode*,int> visited;
    int ans=0;
    int dist;
    void dfs(TreeNode* root,int depth,TreeNode* original){

        if(root==nullptr){
            return;
        }
        visited[root]=1;
            if(leaves[root]==1&&root!=original){
                if(depth<=dist){
                    // cout<<original->val<<':'<<root->val<<":"<<depth<<endl;
                    ans++;
                }else{
                    return;
                }
        }

        if(visited[parent[root]]==0){
            dfs(parent[root],depth+1,original);
        }
        if(visited[root->left]==0){
            dfs(root->left,depth+1,original);
        }

        if(visited[root->right]==0){
            dfs(root->right,depth+1,original);
        }

        return;
    }


    int countPairs(TreeNode* root, int distance) {

        parentMaker(root);
        leafMaker(root);
        dist=distance;


        for(auto iter:leaves){
            visited.clear();
            dfs(iter.first,0,iter.first);

        }



        return ans/2;
    }
};