Comment

avatar username

Let $S$ be the set of all possible graph, $W(G)$ be cost of MST of $G$, $T_{\leq x}(G)$ be the minimum spanning forest form by edges in $G$ with weight $\leq x$, $w_e$ be the weight of an edge. Then we have

$\sum\limits_{G \in S}W(G) = \sum\limits_{G \in S}\sum\limits_{e \in G} w_e = \sum\limits_{G \in S}\sum\limits_{e \in G}\sum\limits_{x = 0}^{M - 1}[w_e > x] = \sum\limits_{x = 0}^{M - 1}\sum\limits_{G \in S}(\#\text{ edges in spanning tree of }G \text{ with weight }> x)$
$= \sum\limits_{x = 0}^{M - 1}\sum\limits_{G \in S}(\# \text{ components in }T_{\leq x}(G) - 1) = \sum\limits_{x = 0}^{M - 1}((\sum\limits_{V \subseteq \{1, 2, \ldots, N\}}(\# \text{ of graph } G \in S \text{ s.t. } V \text{ is an component of }T_{\leq x}(G))) - M^{\binom{N}{2}})$
$= \sum\limits_{x = 0}^{M - 1}\sum\limits_{sz = 1}^N ((\binom{N}{sz}(\# \text{graph } G \in S \text{ s.t. } \{1, 2, \ldots, sz\} \text{ is an component of } T_{\leq x}(G))) - M^{\binom{N}{2}})$

Then the problem reduced to sth similar to this problem, and can be solved by dp.

The actual rating of this user is 2422.

Original comment.

Statistics