Here is the link to the question http://codeforces.com/problemset/problem/431/C in codeforces!!

I don’t get any idea to solve the problem…I tried to understand the editorial but cannot get the idea!!

1 Like

First of let’s see how the to find the answer . We are going to traverse from root node and take those paths which contains atleast one edge having value>=d and sum of edges n. Now , suppose we are node x, then from there we can make k paths having edge value 1,2,…,k respectively. and for each edge we have to check whether it’s grater than or equal to d or not. If it is then we already met the criteria , else we can check further for the condition.

So, recursion solution will look like this - If we have a “sum” of edges in the path and “chk” tells wthere a edge >=d has been visited or not.

int ans=0;

for(i=1 to k) {

if(i>=d) ans=(ans+func(sum+i,1))%M;

else ans=(ans+func(sum+i,chk))%M;

}

Link to my solution - solution

4 Likes

Thanks lashavi!!!