No Abstracts.

# Des.

Calculate the expectation of time complexity of Divide and Conquer when randomly choosing a center of a subtree.

# Sol.

Enumerate the center and the son and calculate the expectation, as $P(i,j) \times 1$ for $j$ is in $i$\’s subtree(in D&C structure). Sum up all $E(i,j)$ is correct.

Convert the problem model again, $j$ is in $i$\’s subtree means that we first chosen $i$ then chosen $j$ ignoring other nodes on that chain between the 2 nodes. So the probability is $\frac{1}{dis(i,j)}$, notice that $P(i,i)$ is 1.

Thus we should calculate the total number of paths of each length, using FFT to boost the process. The time complexity is $O(n \log^2n)$.