```
int Solution::solve(int A, vector<vector<int> > &B)
{
if(A<=3)
return 0;
//to store parent of each node i
int parent[A+1]={0};
parent[1]=-1;
//to store number of edges in the subtree with root i
int edges[A+1]={0};
for(int i=0;i<B.size();i++)
{
parent[B[i][1]]=B[i][0];
edges[B[i][0]]++;
}
for(int i=A;i>1;i--)
edges[parent[i]]+=edges[i];
int ans=0;
for(int i=2;i<=A;i++)
{
if(edges[i]%2==1)
ans++;
}
return ans;
}
```

# Very easy O(n) solution using only arrays

**neuralbot**#1

**lnn_pe8eoz**#2

Explanation for this approach:

We need to count the number of maximum edges that can be removed.

Can this be equivalent to number of subtrees with even nodes ??

Now our task is to find subtrees with even nodes. This can be calculated as number of subtrees with odd number of edges.

i.e. number of nodes in a tree=number of edges+1

Now parent array is used to stare parent of each node.

edges array is used to store number of edges in a particular tree.

In this code

for(int i=0;i<B.size();i++)

{

parent[B[i][1]]=B[i][0];

edges[B[i][0]]++;

}

we are actually adding all the edges that are directly connected to a particular node(node[i] in this case)

for(int i=A;i>1;i–)

edges[parent[i]]+=edges[i];

by this we are adding all the edges directly or indirectly connected to node i

Now in the last part we are just checking whether a particular node has odd or even edges, if it has odd edges , it is a even subtree