# With Map and Recursion

#1

`struct TreeNod
{
int val;
TreeNod* parent;
vector<TreeNod*> childs;
TreeNod(int val):val(val),parent(NULL){}
};

int findMaxEdge(TreeNod* root, int &maxEdge)
{
if(!root)
return 0;

``````vector<int> nodesInChilds;
for(int i = 0; i<root->childs.size(); i++)
nodesInChilds.push_back(findMaxEdge(root->childs[i], maxEdge));

//! if child has even nodes the separate it from root
for(int i = 0; i<nodesInChilds.size(); i++)
{
if(nodesInChilds[i] != 0 && nodesInChilds[i]%2 ==0)
{
root->childs[i] = NULL;
nodesInChilds[i] = 0;
maxEdge++;
}
}

int remainingNodeCount = 0;
for(int i = 0; i<nodesInChilds.size(); i++)
remainingNodeCount += nodesInChilds[i];

return remainingNodeCount + 1; //! +1 for root itself
``````

}

int Solution::solve(int A, vector<vector > &B) {

``````//! Build tree
map<int, TreeNod*> M;

for(int i = 0; i<B.size(); i++)
{
if(M.find(B[i][0]) == M.end())
{
TreeNod* node = new TreeNod(B[i][0]);
M[B[i][0]] = node;
}

if(M.find(B[i][1]) == M.end())
{
TreeNod* node = new TreeNod(B[i][1]);
M[B[i][1]] = node;
}

//! connect edge and parent
M[B[i][0]]->childs.push_back(M[B[i][1]]);
M[B[i][1]]->parent = M[B[i][0]];
}

//! select any node and find root
TreeNod* root = M.begin()->second;

while(root->parent)
{
root = root->parent;
}

int maxEdge = 0;
findMaxEdge(root, maxEdge);

return maxEdge;
``````

}
`