// C++ implementation of the approach 
#include <bits/stdc++.h> 
using namespace std; 

int ans = 0; 

vector<int> graph[100]; 
vector<int> weight(100); 

// Function that returns true if count 
// of set bits in x is even 
bool isEvenParity(int x) 
{ 
    // parity will store the 
    // count of set bits 
    int parity = 0; 
    while (x != 0) { 
        x = x & (x - 1); 
        parity++; 
    } 

    if (parity % 2 == 0) 
        return true; 
    else
        return false; 
} 

// Function to perform dfs 
void dfs(int node, int parent) 
{ 
    // If weight of the current 
    // node has even parity 
    if (isEvenParity(weight[node])) 
        ans += 1; 

    for (int to : graph[node]) { 
        if (to == parent) 
            continue; 
        dfs(to, node); 
    } 
} 

// Driver code 
int main() 
{ 
    // Weights of the node 
    weight[1] = 5; 
    weight[2] = 10; 
    weight[3] = 11; 
    weight[4] = 8; 
    weight[5] = 6; 

    // Edges of the tree 
    graph[1].push_back(2); 
    graph[2].push_back(3); 
    graph[2].push_back(4); 
    graph[1].push_back(5); 

    dfs(1, 1); 

    cout << ans; 

    return 0; 
} 

// Java implementation of the approach  
import java.util.*; 

class GFG 
{ 

static int ans = 0;  

static Vector<Vector<Integer>> graph = new Vector<Vector<Integer>>();  
static Vector<Integer> weight = new Vector<Integer>();  

// Function that returns true if count  
// of set bits in x is even  
static boolean isEvenParity(int x)  
{  
    // parity will store the  
    // count of set bits  
    int parity = 0;  
    while (x != 0)  
    {  
        x = x & (x - 1);  
        parity++;  
    }  

    if (parity % 2 == 0)  
        return true;  
    else
        return false;  
}  

// Function to perform dfs  
static void dfs(int node, int parent)  
{  
    // If weight of the current  
    // node has even parity  
    if (isEvenParity(weight.get(node) )) 
        ans += 1;  

    for (int i = 0; i < graph.get(node).size(); i++)  
    {  
        if (graph.get(node).get(i) == parent)  
            continue;  
        dfs(graph.get(node).get(i) , node);  
    }  
}  

// Driver code  
public static void main(String args[]) 
{  
    // Weights of the node  
    weight.add( 0);  
    weight.add( 5);  
    weight.add( 10);;  
    weight.add( 11);;  
    weight.add( 8);  
    weight.add( 6);  

    for(int i=0;i<100;i++) 
    graph.add(new Vector<Integer>()); 

    // Edges of the tree  
    graph.get(1).add(2);  
    graph.get(2).add(3);  
    graph.get(2).add(4);  
    graph.get(1).add(5);  

    dfs(1, 1);  

    System.out.println( ans );  

} 
} 

// This code is contributed by Arnab Kundu 

# Python3 implementation of the approach 
ans = 0

graph = [[] for i in range(100)] 
weight = [0]*100

# Function that returns True if count 
# of set bits in x is even 
def isEvenParity(x): 

    # parity will store the 
    # count of set bits 
    parity = 0
    while (x != 0): 
        x = x & (x - 1) 
        parity += 1

    if (parity % 2 == 0): 
        return True
    else: 
        return False

# Function to perform dfs 
def dfs(node, parent): 
    global ans 

    # If weight of the current 
    # node has even parity 
    if (isEvenParity(weight[node])): 
        ans += 1

    for to in graph[node]: 
        if (to == parent): 
            continue
        dfs(to, node) 

# Driver code 

# Weights of the node 
weight[1] = 5
weight[2] = 10
weight[3] = 11
weight[4] = 8
weight[5] = 6

# Edges of the tree 
graph[1].append(2) 
graph[2].append(3) 
graph[2].append(4) 
graph[1].append(5) 

dfs(1, 1) 
print(ans) 

# This code is contributed by SHUBHAMSINGH10 

// C# implementation of the approach  
using System; 
using System.Collections.Generic; 

class GFG 
{ 

static int ans = 0;  

static List<List<int>> graph = new List<List<int>>(); 
static List<int> weight = new List<int>(); 

// Function that returns true if count  
// of set bits in x is even  
static bool isEvenParity(int x)  
{  
    // parity will store the  
    // count of set bits  
    int parity = 0;  
    while (x != 0)  
    {  
        x = x & (x - 1);  
        parity++;  
    }  

    if (parity % 2 == 0)  
        return true;  
    else
        return false;  
}  

// Function to perform dfs  
static void dfs(int node, int parent)  
{  
    // If weight of the current  
    // node has even parity  
    if (isEvenParity(weight[node])) 
        ans += 1;  

    for (int i = 0; i < graph[node].Count; i++)  
    {  
        if (graph[node][i] == parent)  
            continue;  
        dfs(graph[node][i] , node);  
    }  
}  

// Driver code  
static void Main() 
{  
    // Weights of the node  
    weight.Add(0);  
    weight.Add(5);  
    weight.Add(10); 
    weight.Add(11); 
    weight.Add(8);  
    weight.Add(6);  

    for(int i = 0; i < 100; i++) 
    graph.Add(new List<int>()); 

    // Edges of the tree  
    graph[1].Add(2);  
    graph[2].Add(3);  
    graph[2].Add(4);  
    graph[1].Add(5);  

    dfs(1, 1);  

    Console.WriteLine( ans );  
} 
} 

// This code is contributed by mits 

3