Codeforces-K-Tree?

general
1

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!!

2

Here is the working link of question http://codeforces.com/problemset/problem/431/C

1 Like
3

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

2 Likes
4

Thanks lashavi!!!