Construct a Tree whose sum of nodes of all the root to leaf path is not divisible by the count of nodes in that path | C ++ program for the above approach ; Function to assign values to nodes of the tree s . t . sum of values of nodes of path between any 2 nodes is not divisible by length of path ; Stores the adjacency list ; Create a adjacency list ; Stores whether node is visited or not ; Stores the node values ; Variable used to assign values to the nodes alternatively to the parent child ; Declare a queue ; Push the 1 st node ; Assign K value to this node ; Dequeue the node ; Mark it as visited ; Upgrade the value of K ; Assign K to the child nodes ; If the child is unvisited ; Enqueue the child ; Assign K to the child ; Print the value assigned to the nodes ; Driver Code ; Function Call
#include " bits / stdc + + . h " NEW_LINE using namespace std ; void assignValues ( int Edges [ ] [ 2 ] , int n ) { vector < int > tree [ n + 1 ] ; for ( int i = 0 ; i < n - 1 ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; tree [ u ] . push_back ( v ) ; tree [ v ] . push_back ( u ) ; } vector < bool > visited ( n + 1 , false ) ; vector < int > answer ( n + 1 ) ; int K = 1 ; queue < int > q ; q . push ( 1 ) ; answer [ 1 ] = K ; while ( ! q . empty ( ) ) { int node = q . front ( ) ; q . pop ( ) ; visited [ node ] = true ; K = ( ( answer [ node ] == 1 ) ? 2 : 1 ) ; for ( auto child : tree [ node ] ) { if ( ! visited [ child ] ) { q . push ( child ) ; answer [ child ] = K ; } } } for ( int i = 1 ; i <= n ; i ++ ) { cout << answer [ i ] << " ▁ " ; } } int main ( ) { int N = 11 ; int Edges [ ] [ 2 ] = { { 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 1 , 5 } , { 2 , 6 } , { 2 , 10 } , { 10 , 11 } , { 3 , 7 } , { 4 , 8 } , { 5 , 9 } } ; assignValues ( Edges , N ) ; return 0 ; }