Observation :- As m=n-1 . Therefore we need to create a tree. Since we are considering shortest path in a tree from root to a certain vertex v, it means there should be a[v] vertex in its path or we can call a[v] as its level. Since it will only have a single parent ( as it is a tree) the edge should come from a vertex that is at level a[v]-1. So we have (count(nodes with a[i]= a[v]-1)) options for parent of this vertex. To answer this subtask we just have to multiply this to the answer for every vertex from 2 to n.
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 ?
Subtask 2:- Now we do not have the condition that m=n-1 therefore there can be additional edges. Now as given in the problem statement that it should only have a single shortest path therefore it should only have a single edge connected to a vertex that has a[i]=a[v]-1. In this way we can select n-1 edges.
Now we have to explore the options for remaining m-n+1 edges . Lets say for current vertex v it has a edge from a vertex u and this hasn’t been selected yet.
What can be the value of a[u]:-
- a[u]==a[v]-1 we can’t select this edge as we want unique shortest path from 1 to v and one vertex with value a[x]=a[v]-1 has already been selected.
- a[u]< a[v]-1 if we select this edge the shortest path to v will have length a[u]+1 and which will not be equal to a[v]
- a[u]==a[v] Now if we select this edge the shortest path to v will still remain a[v] and same can be said for shortest path from 1 to u.
- a[u]>a[v] We can explore it later for when we will deal with u.
Now we can only select the edges which are in between two vertex have same value a[u]==a[v].
Now we just need to count total number of edges of this type (let’s say it as tot)and multiply tot choose (m-n+1) to our answer.
For calculating tot
int tot =0;
int cnt =number of vertices with a[v]==i
For calculating tot choose (m-n+1) :-
as we know nCr = (n/r )*(n-1Cr-1) ->we can simply write nCr as
(n * (n-1) * (n-2) * (n-3) *…(n-r+1))/(r * (r-1) * (r-2)…2 * 1)
Since m-n+1 will be less thatn 2e5 ,above numerator and denominator can be calculated under time limit . Then we just have to multiply numerator * ( inverse (denominator)) to the answer .
Where inverse ( c ) represent power(c,MOD-2)
You can see my code here :-https://www.codechef.com/viewsolution/37267460