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 | Python3 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 any 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
from collections import deque NEW_LINE def assignValues ( Edges , n ) : NEW_LINE INDENT tree = [ [ ] for i in range ( n + 1 ) ] NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT u = Edges [ i ] [ 0 ] NEW_LINE v = Edges [ i ] [ 1 ] NEW_LINE tree [ u ] . append ( v ) NEW_LINE tree [ v ] . append ( u ) NEW_LINE DEDENT visited = [ False ] * ( n + 1 ) NEW_LINE answer = [ 0 ] * ( n + 1 ) NEW_LINE K = 1 NEW_LINE q = deque ( ) NEW_LINE q . append ( 1 ) NEW_LINE answer [ 1 ] = K NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT node = q . popleft ( ) NEW_LINE visited [ node ] = True NEW_LINE K = 2 if ( answer [ node ] == 1 ) else 1 NEW_LINE for child in tree [ node ] : NEW_LINE INDENT if ( not visited [ child ] ) : NEW_LINE INDENT q . append ( child ) NEW_LINE answer [ child ] = K NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( answer [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 7 NEW_LINE Edges = [ [ 1 , 2 ] , [ 4 , 6 ] , [ 3 , 5 ] , [ 1 , 4 ] , [ 7 , 5 ] , [ 5 , 1 ] ] NEW_LINE assignValues ( Edges , N ) NEW_LINE DEDENT