Count nodes having Bitwise XOR of all edges in their path from the root equal to K | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static Vector < pair > [ ] adj = new Vector [ 100005 ] ; static int visited [ ] = new int [ 100005 ] ; static int ans = 0 ; static void dfs ( int node , int xorr , int k ) { visited [ node ] = 1 ; if ( node != 1 && xorr == k ) ans ++ ; for ( pair x : adj [ node ] ) { if ( visited [ x . first ] != 1 ) { int xorr1 = xorr ^ x . second ; dfs ( x . first , xorr1 , k ) ; } } } static void countNodes ( int N , int K , int R , 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 ] . add ( new pair ( v , w ) ) ; adj [ v ] . add ( new pair ( u , w ) ) ; } dfs ( R , 0 , K ) ; System . out . print ( ans + "NEW_LINE"); } public static void main ( String [ ] args ) { int K = 0 , R = 1 ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < pair > ( ) ; int [ ] [ ] edges = { { 1 , 2 , 3 } , { 1 , 3 , 1 } , { 2 , 4 , 3 } , { 2 , 5 , 4 } , { 3 , 6 , 1 } , { 3 , 7 , 2 } } ; int N = edges . length ; countNodes ( N , K , R , edges ) ; } }