Subtask 1:-

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.

OR :-

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;

fr(i,1, max(a[v]))

{

int cnt =number of vertices with a[v]==i

tot+= cnt*(cnt-1)/2;

}

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