16 minutes ago

Rohit • 0

Hyderabad

Question: Lucky Path

Problem Statement:

You are given a tree with N nodes rooted at node 1. Each node has an integer value value[i].

A lucky path is defined as a path from the root to any leaf such that the sum of all node values on that path is divisible by K.

Find the total number of lucky paths in the tree.

Notes:

• A tree is a connected acyclic graph with N nodes and N - 1 edges.

Input Format:

• The first line contains an integer, N, denoting the number of nodes.
• The next line contains an integer, K.
• Each line i of the N subsequent lines (where 0 <= i < N) contains 2 space-separated integers each describing the row Edges[i], the edge (0,0) must be ignored.
• (Further input lines will contain the node values).