Problem Statement   This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.
Manao is studying graph theory and simple cycles in particular. A simple cycle of length L ≥ 3 in graph G is a sequence of vertices (v_{0}, v_{1}, ..., v_{L1}) such that all v_{0}, v_{1}, ..., v_{L1} are pairwise distinct and for each i=0..L1, an edge between v_{i} and v_{(i+1) mod L} exists in G.
Manao is interested in graphs formed by connecting two trees. The connection process is as follows. Manao takes two trees composed of N vertices each. The vertices in each tree are labeled from 0 to N  1. Then, he generates a permutation P of numbers from 0 to N  1 uniformly at random. Finally, the graph is formed by connecting vertex i of the first tree to vertex P[i] of the second tree, for each i from 0 to N  1. To remove ambiguity, the vertices of the first tree within the graph are referred to as A_{0}, A_{1}, ..., A_{N1} and the vertices of the second graph are referred to as B_{0}, B_{1}, ..., B_{N1}. Manao wants to know the expected number of simple cycles of length K in the resulting graph.
You are given two String[]s, tree1 and tree2. Merge the elements of tree1 to obtain a single string formatted as a spaceseparated list of N  1 integers describing the first tree. Let x[i] denote the ith integer (0based index) in the list. Then, for each i, we have 0 ≤ x[i] ≤ i and in our tree the vertices x[i] and i+1 are connected by an edge. tree2 describes the second tree in the same fashion.
Compute and return the expected number of simple cycles of length K in the graph formed by connecting the two given trees as described above. Two simple cycles are equal if one of them can be cyclically shifted, or reversed and cyclically shifted, to coincide with the second. According to this definition, (1, 2, 3, 4), (2, 3, 4, 1) and (3, 2, 1, 4) are all equal.   Definition   Class:  TreeUnion  Method:  expectedCycles  Parameters:  String[], String[], int  Returns:  double  Method signature:  double expectedCycles(String[] tree1, String[] tree2, int K)  (be sure your method is public) 
    Notes    The returned value must have an absolute or relative error less than 1e9.   Constraints    The concatenation of elements of tree1 will be formatted as a spaceseparated list of N  1 integers, where N is between 2 and 300, inclusive.    tree1 will contain between 1 and 50 elements, inclusive.    Each element of tree1 will be between 1 and 50 characters long, inclusive.    For each i, the ith integer (0based index) in the concatenation of elements of tree1 will be between 0 and i, inclusive, and will have no extra leading zeros.    The concatenation of elements of tree2 will be formatted as a spaceseparated list of N  1 integers, where N is between 2 and 300, inclusive.    tree2 will contain between 1 and 50 elements, inclusive.    Each element of tree2 will be between 1 and 50 characters long, inclusive.    For each i, the ith integer (0based index) in the concatenation of elements of tree2 will be between 0 and i, inclusive, and will have no extra leading zeros.    K will be between 3 and 7, inclusive.   Examples  0)     Returns: 1.0  Manao has two trees with two vertices each. He can connect them in two ways:
Either way, the resulting graph is a single cycle of length 4. 

 1)     Returns: 1.3333333333333333  Manao has two chains composed of three vertices each. There are 6 possible permutations which result in the following graphs:
Each of the two graphs shown in the topmost row contains two cycles of length 4.
(Note that in each case the two cycles share the edge A_{1}B_{1}.)
Each of the other four graphs only contains one cycle of length 4.
Thus the expected number of cycles of length 4 is (2+2+1+1+1+1)/6 = 8/6 = 1.3333333333. 

 2)     Returns: 0.3333333333333333  These are the same trees as in the previous example, but this time Manao is looking for simple cycles with 6 vertices. Only the topmost two graphs contain a cycle of length 6, thus the expected number of such cycles for a random permutation P is 1/3. 

 3)    {"0 ", "1 1 1"}  {"0 1 0 ", "1"}  5 
 Returns: 4.0  The corresponding trees are these:


 4)    {"0 1 2 0 1 2 0 1 2 5 6 1", "0 11", " 4"}  {"0 1 1 0 2 3 4 3 4 6 6", " 10 12 12"}  7 
 Returns: 13.314285714285713  Do not forget to concatenate the elements of the lists first. 


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
