Question

You are given a tree (rooted at node ) with nodes. For each vertex , find the number of paths of odd and even length which pass the vertex and lie in its subtree. Length of a path is defined as the number of edges in it. Subtree of a node is the set of nodes, such that lies in the path from root to . Path a and b are considered distinct if either a or b contains some edge that other do not contain.

Answer 1

Answer:

Step-by-step explanation:

Expalnation: First we should calculate value count[s] : the number of nodes in subtree of node s. Where subtree contains the node itself and all the nodes in the subtree of its children. Thus, we can calculate the number of nodes recursively using concept of DFS and DP, where we should process each edge only once and count[] value of a children used in calculating count[] of its parent expressing the concept of DP(Dynamic programming).

Time Complexity : O(n) [in processing of all (n-1) edges].

Hope it helps you...