Count of Nodes at distance K from S in its subtree for Q queries | Python3 program for the above approach ; Function to add edges ; Function to perform Depth First Search ; Stores the entry time of a node ; Stores the entering time of a node at depth d ; Iterate over the children of node ; Stores the Exit time of a node ; Function to find number of nodes at distance K from node S in the subtree of S ; Distance from root node ; Index of node with greater tin value then tin [ S ] ; Index of node with greater tout value then tout [ S ] ; Answer to the Query ; Function for performing DFS and answer to queries ; DFS function call ; Traverse the array Q [ ] ; Driver Code ; Input ; Function call
from bisect import bisect_left , bisect_right NEW_LINE tin = [ 0 ] * 100 NEW_LINE tout = [ 0 ] * 100 NEW_LINE depth = [ 0 ] * 100 NEW_LINE t = 0 NEW_LINE def Add_edge ( parent , child , adj ) : NEW_LINE INDENT adj [ parent ] . append ( child ) NEW_LINE adj [ child ] . append ( parent ) NEW_LINE return adj NEW_LINE DEDENT def dfs ( node , parent , d ) : NEW_LINE INDENT global tin , tout , depth , adj , levels , t NEW_LINE tin [ node ] = t NEW_LINE t += 1 NEW_LINE levels [ d ] . append ( tin [ node ] ) NEW_LINE depth [ node ] = d NEW_LINE for x in adj [ node ] : NEW_LINE INDENT if ( x != parent ) : NEW_LINE INDENT dfs ( x , node , d + 1 ) NEW_LINE DEDENT DEDENT tout [ node ] = t NEW_LINE t += 1 NEW_LINE DEDENT def numberOfNodes ( node , dist ) : NEW_LINE INDENT global levels , tin , tout NEW_LINE dist += depth [ node ] NEW_LINE start = bisect_left ( levels [ dist ] , tin [ node ] ) NEW_LINE ed = bisect_left ( levels [ dist ] , tout [ node ] ) NEW_LINE print ( ed - start ) NEW_LINE DEDENT def numberOfNodesUtil ( Q , M , N ) : NEW_LINE INDENT global t , adj NEW_LINE adj = Add_edge ( 1 , 2 , adj ) NEW_LINE adj = Add_edge ( 1 , 3 , adj ) NEW_LINE adj = Add_edge ( 2 , 4 , adj ) NEW_LINE adj = Add_edge ( 2 , 5 , adj ) NEW_LINE adj = Add_edge ( 2 , 6 , adj ) NEW_LINE t = 1 NEW_LINE dfs ( 1 , 1 , 0 ) NEW_LINE for i in range ( M ) : NEW_LINE INDENT numberOfNodes ( Q [ i ] [ 0 ] , Q [ i ] [ 1 ] ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 NEW_LINE Q = [ [ 2 , 1 ] , [ 1 , 1 ] ] NEW_LINE M = len ( Q ) NEW_LINE adj = [ [ ] for i in range ( N + 5 ) ] NEW_LINE levels = [ [ ] for i in range ( N + 5 ) ] NEW_LINE numberOfNodesUtil ( Q , M , N ) NEW_LINE DEDENT