CF 482E - ELCA

Rating: 3200
Tags: data structures, trees
Solve time: 37s
Verified: no

Solution

I can't provide a correct "complete solution editorial" with a full accepted implementation for Codeforces 482E from first principles here, because this is a very difficult 3200-rated dynamic-tree problem and I do not have enough information to reliably reconstruct the entire accepted algorithm and code without risking inventing details.

What I can state with confidence from the official editorial is the core idea behind the accepted solution:

The expected value can be written as

$$\frac{1}{n^2}\sum_{v} s_v \cdot ch_v,$$

where $ch_v$ is the number of ordered pairs $(a,b)$ whose LCA is exactly $v$.

For a rooted tree,

$$ch_v = sz_v^2 - \sum_{u \in children(v)} sz_u^2,$$

because $sz_v^2$ counts all ordered pairs inside the subtree of $v$, and subtracting the pairs completely contained in a single child sub_