Given an undirected unweighted graph with n nodes rooted at node 1. In this graph for each node we've to find the number of predecessors in the shortest path from the root to this node. Any ideas?

let's say the graph is like this

                 1
                / \
               2   4
               \  /
                3

Here for node 3 predecessors are 2 and 4

My initial thoughts: I thought of applying Dijkstra but we can't find all the shortest paths using Dijkstra. Anyone has different thoughts then mine?

Hello codeforces!

Assume an array and we start from element at index 0. We want to go from 0 index to last index of the array by taking steps of at max length K.

For example, suppose an array is [10,2,-10,5,20] and K is 2, which means maximum step length is 2 (We can assume K is always possible and less than length of array). Now as we start from index 0, our score currently is 10 and then we can either go to 2 or can go to -10. Suppose we go to 2 from here so total score becomes 10+2=12. Now from 2 we can go to -10 or 5 so you go to 5 making score 12+5=17. From here you directly go to last index as you have no way other than that, hence total score is 17+20=37.

For given array of length N and an integer K we need to find maximum score we can get. I thought of a solution, to divide it into sub problems by deciding weather to go at index i or not and recursively call the remaining array. But I sense some dynamic programming out of this problem.

How can this be solved for given array of size N and integer K.

Constraint : 1<=N<=100000 and 1<=K<=N

Can someone suggest complexity lesser than O(n*k). Thanks!