SRM 581 div 1 level 2 TreeUnion

Problem statement 

I counted all the possible number of k cycles . Now since we are connecting two trees so when will a cycle form ? it will form when two nodes connected in tree1 are connected to two nodes of tree2 which have a path between them.

e.g suppose tree1 : aà bà cà d      tree2 : pàqàràs

suppose we connect  a  to  q  and  c  to  s ,  so it will be cycle of length 6  aàbàcàsàràqàa

similarly if  we connect  b to p and d to q it will be a cycle of length 5, bàcàdà qàp

length of  cycle =sum of  number of nodes b/w first node to second node  in tree1 or dis1[node1][node2]+1  and number of nodes b/w first node to second node of tree2 dis2[node1][node2].

We can find the distance between each pair of nodes in respective node using floyad warshall ,since maximum number of nodes is only 300.

Since cycle length is exactly k, so our expected value =  total number of cycles of length k divided by total number of permutation which is n! .

For tree1 and tree2 we keep cnt1[][] and cnt2[][]

For each node I in tree1 cnt1[i][j] is number of nodes which is at a distance j from i

Similarly cnt2[i][j] is filled.

Now basically the idea is to match 2 nodes in tree1 at distance d1 to 2 nodes in tree2 at distance d2 such that d1+d2+2=k

 -----------------------------------------------------------------------------------------------------------------------------

  import java.util.*;

   import static java.lang.Math.*;

public class TreeUnion {

                public double expectedCycles(String[] tree1, String[] tree2, int K) {

        int cnt1[][]=fill(tree1);

        int cnt2[][]=fill(tree2);

        int n=cnt1.length;

        double mul=1.0/(n*(n-1)),ans=0;

        for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=1;k<K-2;k++)ans+=2*mul*cnt1[i][k]*cnt2[j][K-2-k];

                                return ans;

                }

    int[][] fill(String tree1[])

    {

        StringBuilder sb=new StringBuilder();

        for(String s:tree1)  sb.append(s);

        String s[]=sb.toString().split(" ");

        int n=s.length,inf=1<<25;

        int dis1[][]=new int[n+1][n+1];

        for(int i[]:dis1)Arrays.fill(i,inf);

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

        {

            int p=Integer.parseInt(s[i]);

            dis1[i+1][p]=dis1[p][i+1]=1;

        }

        for(int k=0;k<=n;k++)for(int i=0;i<=n;i++)for(int j=0;j<=n;j++) 

        dis1[i][j]=min(dis1[i][j],dis1[i][k]+dis1[k][j]);

        int cnt[][]=new int[n+1][6];

        for(int i=0;i<=n;i++)for(int j=i+1;j<=n;j++)if(dis1[i][j]<6)cnt[i][dis1[i][j]]++;

        return cnt;

    }

}