The point is that k <= 7. So it easy to proof that there would be exactly 2 edges between different trees in any cycle. Now we just need to calc d[x] — how many path of lenth x there are in both trees and the answer would be summ (x = 1 .. K — 3) 2 * d1[x] * d2[k — 2 — x] / n / (n — 1).