Count nodes having Bitwise XOR of all edges in their path from the root equal to K | C ++ program for the above approach ; Initialize the adjacency list to represent the tree ; Marks visited / unvisited vertices ; Stores the required count of nodes ; DFS to visit each vertex ; Mark the current node as visited ; Update the counter xor is K ; Visit adjacent nodes ; Calculate Bitwise XOR of edges in the path ; Recursive call to dfs function ; Function to construct the tree and print required count of nodes ; Add edges ; Print answer ; Driver Code ; Given K and R ; Given edges ; Number of vertices ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < pair < int , int > > adj [ 100005 ] ; int visited [ 100005 ] = { 0 } ; int ans = 0 ; void dfs ( int node , int xorr , int k ) { visited [ node ] = 1 ; if ( node != 1 && xorr == k ) ans ++ ; for ( auto x : adj [ node ] ) { if ( ! visited [ x . first ] ) { int xorr1 = xorr ^ x . second ; dfs ( x . first , xorr1 , k ) ; } } } void countNodes ( int N , int K , int R , vector < vector < int > > edges ) { for ( int i = 0 ; i < N - 1 ; i ++ ) { int u = edges [ i ] [ 0 ] , v = edges [ i ] [ 1 ] , w = edges [ i ] [ 2 ] ; adj [ u ] . push_back ( { v , w } ) ; adj [ v ] . push_back ( { u , w } ) ; } dfs ( R , 0 , K ) ; cout << ans << " STRNEWLINE " ; } int main ( ) { int K = 0 , R = 1 ; vector < vector < int > > edges = { { 1 , 2 , 3 } , { 1 , 3 , 1 } , { 2 , 4 , 3 } , { 2 , 5 , 4 } , { 3 , 6 , 1 } , { 3 , 7 , 2 } } ; int N = edges . size ( ) ; countNodes ( N , K , R , edges ) ; return 0 ; }