To answer this subtask we just have to multiply this to the answer for every vertex from 2 to n.
can you taken an example to elaborate ?
You just have to consider it as a tree rooted at 1. Now to find the shortest path to any vertex v from root you just have to find its level right?
if its level is (say lev[v]) it’s parent must be a vertex with level (lev[v]-1 ). So you can choose any vertex with level lev[v]-1 as its parent. we can say that we have (cnt(number of nodes at level lev[v]-1)) options. By basic PnC rules we just have to multiply these options right ?
Tell me if you want more explanation. I will be happy to help.
1 Like
Excellent explanation man. I missed the “single shortest path” condition and complicated the problem.
3 Likes
I cannot find the editorial for other questions? Have they been uploaded yet?
2 Likes
While calculating \binom{tot}{m-n+1}, how will you calculate tot!? I am asking this to you because, tot can be as high as \relax10^{10} and it won’t be calculated in time.
1 Like
Awesome editorial bro !!
2 Likes
I have written it in the editorial itself.
It is just the number of edges in between the vertices with same value in the array.
So we just have to sum all those edges . Let say there are cnt number of vertex with value x we just have to add cnt*(cnt-1) in the tot. and x can only be from 1 to max value in our array which is definitely less than n. So we can find tot in O(n) time complexity.
1 Like
But if you are asking about calculating tot choose (m-n+1) since tot is very large… See we can find nCr in O(min(r,n-r)). And the method has already been mentioned in the editorial.
2 Likes
Let’s say we have 3 nodes at level 2( or shortest distance 1 from node 1) and 2 nodes at level 3( or shortest distance 2 from node 1) then I think there are 9(3 ^ 2) ways to connect the nodes at level 2 and level 3. Note that I am not considering now the other edges which can be between the nodes of the same level (because this case will be considered later in the part where we are selecting m-n+1 nodes from total edges).
Let’s say nodes at level 2 are 2, 3 and 4
and noes at level 3 are 5 and 6
According to me the 9 possibilities are :-
2 - 5, 2 - 6
2 - 5, 3 - 6
2 - 5, 4 - 6
3 - 5, 2 - 6
3 - 5, 3 - 6
3 - 5, 4 - 6
4 - 5, 2 - 6
4 - 5, 3 - 6
4 - 5, 4 - 6
I know it is wrong but i don’t know my mistake and i also don’t know how you are calculating 6 (3 * 2) ways to connect the nodes. Please tell me what I am doing wrong?
1 Like
didn’t see the constraints that M < 2e5 and wasted 1/2 hr during contest 
You are absolutely right, the answer for above scenerio comes out to be 9. And even I am calculating it to be 9.
Yeah I got it thanks 
.
UPD : Very nice explanation and clean editorial.
1 Like
can anyone explain this -> cnt*(cnt-1)/2; why div by 2?
it is cnt C 2.
Let say there are v vertex and you have to find total number of edges between them, how will you find it. You can choose 2 vertices out of this v right and there will be a edge between them, the number of ways to choose these two vertices is cnt C 2. You can learn more about how to select r things out of n things from the internet.
yes i got it…thanks
1 Like
Yeah, I misunderstood your code, sorry for that. But still I am getting TLE in subtask 2 although i have calculated NCR in min(r, n-r) complexity. So can you please have a look at my code?
My code is very clean and commented as well, so it won’t be very difficult for you to go through my code.
https://www.codechef.com/viewsolution/37361149
just take i of long long type while calculating numerator and denominator and multiply (i%mod) instead of just i (since i can be of range 10^10 and answer can be as high as 10^9 which might cause integer overflow) in numerator and denominator
1 Like
Thanks a lot for your help
1 Like