TopCoder SRM581: TreeUnion

public class TreeUnion {
    const int inf = 1 << 28;

    int[,] Convert(string[] tree) {
        var array = String.Concat(tree).Split().Select(int.Parse).ToArray();
        int n = array.Length + 1;
        int[,] d = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i, j] = inf;
            }
            d[i, i] = 0;
        }
        for (int i = 0; i < array.Length; i++) {
            d[i + 1, array[i]] = 1;
            d[array[i], i + 1] = 1;
        }
        return d;
    }

    void warshallFloyd(int[,] d) {
        int n = d.GetLength(0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    d[j, k] = Math.Min(d[j, k], d[j, i] + d[i, k]);
                }
            }
        }
    }

    private static int[] ToDistanceMap(int n, int[,] d, int a) {

        int[] distanceHist = new int[n + 1];
        for (int k = 0; k < n; k++) {
            if (d[a, k] < inf && a != k)
                distanceHist[d[a, k]]++;
        }
        return distanceHist;
    }

    public double expectedCycles(string[] tree1, string[] tree2, int K) {
        int[,] d1 = Convert(tree1);
        int[,] d2 = Convert(tree2);
        int n = d1.GetLength(0);
        warshallFloyd(d1);
        warshallFloyd(d2);

        double ans = 0;

        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                var distanceHistA = ToDistanceMap(n, d1, a);
                var distanceHistB = ToDistanceMap(n, d2, b);
                for (int i = 0; i <= K; i++) {
                    if (i == 0 || K - 2 - i <= 0) continue;
                    ans += 1.0 * distanceHistA[i] * distanceHistB[K - 2 - i];
                }
            }
        }

        return ans / (n * (n - 1)) / 2.0;
    }
}