/**
 * 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:
    vector<int> graph[100010];
    int vall[100010];
    // memset(vall,0,sizeof(vall));
    int node=1;
    void run(TreeNode* root)
    {
        if(root==NULL) return;
        int curr_par=node;
        vall[node++]=root->val;
        if(root->left!=NULL){ graph[curr_par].push_back(node); graph[node].push_back(curr_par); }
        run(root->left);
        if(root->right!=NULL){ graph[curr_par].push_back(node); graph[node].push_back(curr_par); }
        run(root->right);
    }
    vector<int> path;
    int par[100010];
    int depth[100010];
    void dfs(int v, int p, int d, vector<int> graph[])
    {
        depth[v]=d;
        par[v]=p;
        for(auto c:graph[v])
        {
            if(c!=p)
            {
                dfs(c,v,d+1,graph);
            }
        }
    }
    void getpath(int a, int b)
    {
        vector<int> path2;
        path.push_back(a);
        path2.push_back(b);
        while(a!=b)
        {
            if(depth[a]<depth[b])
            {
                path2.push_back(b=par[b]);
            }
            else if(depth[a]>depth[b])
            {
                path.push_back(a=par[a]);
            }
            else if(depth[a]==depth[b])
            {
                path.push_back(a=par[a]);
                path2.push_back(b=par[b]);
            }
        }
        //reverse(path2.begin(),path2.end());
        path2.erase(path2.begin()+int(path2.size())-1);
        path.insert(path.end(),path2.begin(),path2.end());
        //return path1;
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        run(root);
        vector<int> leaves;
        for(int i=2; i<100010; i++)
        {
            if(graph[i].size()==1) leaves.push_back(i);
        }
        dfs(1,0,0,graph);
        int ans=0;
        if(leaves.empty()) ans++;
        for(auto x:leaves)
        {
            // cout<<vall[x]<<endl;
            path.clear();
            getpath(1,x);
            int countt[10];
            memset(countt,0,sizeof(countt));
            for(auto x:path)
            {
                // cout<<x<<" ";
                countt[vall[x]]++;
            }
            // cout<<endl;
            int odd=0;
            for(int i=1; i<10; i++)
            {
                if(countt[i])
                {
                    if(countt[i]%2) odd++;
                }
            }
            if(int(path.size())%2)
            {
                if(odd==1) ans++;
            }
            else
            {
                if(odd==0) ans++;
            }
        }
        return ans;
    }
};