Problem Statement

Delhi metro has n stations connected by roads between them. The underlying network of roads between the stations has a tree structure. For each road u,v, there is a fare for going from station u to station v.

Devu wants to travel by metro, so he is currently at station 1. In a single step, he can uniformly randomly go to any of the neighbouring stations of the current station.

The metro charges you based on the starting and ending station regardless of the actual distance you might have travelled. So the fare charged from you for a journey will be the total fare of roads on the path from start to end station.

Find out the expected fare of his journey having a total of k steps.

Input Format

• The first line contains an integer T, that is the number of test cases.
• For each test case
  • The first line contains two space-separated integers, n,k, as defined in the problem statement.
  • In the next n−1 lines, each line contains three space-separted integers u,v,wdenoting that there is a road between station u to v with fare equal to w.

Output Format

For each test case, print a real number having absolute or relative error of 1e-6.

Constraints

• 1≤T≤50
• 2≤n,k≤50
• 1≤w≤109
• 1≤u,v≤n
• It is guaranteed that there is no multi-edge and self-loop in the given input.

Sample Input

2
2 1
1 2 4
2 2
1 2 4

Sample Output

4.000000
0.000000

Explanation

• In the first example, you can only go station 2 from station 1 in a single step. So the fare charged from you will be 4.
• In the second example, you can go from station 1 to station 1 again in two steps. So the fare charged from you is zero.

This can be done with a 2D dp where the state is dp[i][j] meaning going to ith node at jth step.

We observe that dp[1][0]=1.00 as initially we start with 1.

The we go for an o(n^3) solution which tries go traverse at ith node from kth node and the probability of doing such is 1/number of edges.

code here

#include<bits/stdc++.h>

using namespace std;

long long int dist[70];

bool vis[70];

double dp[60][60];

bool connect[60][60];

#define mp make_pair

#define pb push_back

#define ff first

#define ss second

int cnt[60];

void fill(int st,list<pair<int,int> >arr[])

{

vis[st]=1;

dist[st]=0;

stack<int> s;

s.push(st);

while(!s.empty())

{

   int a=s.top();

   s.pop();

    list<pair<int,int> > ::iterator it;

   for(it=arr[a].begin();it!=arr[a].end();it++)

   {

    if(!vis[it->ff])

    {

    vis[it->ff]=1;

    dist[it->ff]=dist[a]+it->ss;

    s.push(it->ff);

     }

    }

}

}

int main()

{

int t;

// freopen("ans.txt","w",stdout);

cin>>t;

while(t--)

{int n,a,b,w;

cin>>n;

int k;

cin>>k;

list<pair<int,int> >arr[100];

memset(cnt,0,sizeof(cnt));

memset(connect,0,sizeof(connect));

for(int i=0;i<n-1;i++)

{

cin>>a>>b>>w;

cnt[a]++;

cnt[b]++;

arr[a].pb(mp(b,w));

arr[b].pb(mp(a,w));

connect[a][b]=1;

connect[b][a]=1;

}

memset(vis,0,sizeof(vis));

fill(1,arr);

/*for(int i=1;i<=n;i++)

{

cout<<dist[i]<<" ";

}

cout<<endl;*/

dp[1][0]=1.00;

for(int i=1;i<=n+2;i++)

{

for(int t=1;t<=k+2;t++ )

dp[i][t]=0.00;

}

dp[1][0]=1.00;

for(int i=1;i<=k;i++)

{

 for(int nodes=1;nodes<=n;nodes++)

 {

  for(int from=1;from<=n;from++)

  {

             double p=(double)cnt[from];

    if(from!=nodes && connect[from][nodes]==1)

    {

         dp[nodes][i]+=(dp[from][i-1])/p;

     }

}

 }

}

double ans=0.00;

for(int i=1;i<=n;i++)

{

  double dt=(double)(dist[i]-dist[1]);

  ans+=dt*dp[i][k];

}

printf("%.12lf\n",ans);

}

return 0;

}