恩，大概是这么个问题：

给定一个图，每次对于一个联通块，随机删除一棵生成树，期望多少次删完所有的边？

于是想了一下没有结果，打个程序试试，发现随机图上差不多就是 $m/n$ 了。

关于这个数，xhr 说一定不超过原图两点间最大流的最大值，因为每次起码会破坏一条增广路。

然后呢？不知道了。

于是乎 xhr 又 YY 了一个题（据 Vani 说是 Asia Regional 2012 Chengdu 的原题）：

给定一个图 $G = (V, E)$ ，保证 $\|E\| \leq 5\|V\|$ ，每次修改一个点，查询一个点所有邻居的权和。

$\|V\| \leq 2 \times 10^4, Q \leq 10^6$

有了这个 图树剖分 还是蛮简单的吧。

我肿么感觉我就是打了一圈酱油呢？

update

从网上找到篇论文： Disjoint Spanning Trees 1 Forest Partitioning

里面有这么句话：

The minimum number of forests needed to cover the edges of a graph $G$ is

$$\max \{\lceil\|A\| / \text{rank}(A) \rceil: A \in E\}.$$

其中 $\mathnormal{rank}(A)$ 的定义是 $A$ 的顶点数减去连通块个数。

也就是说，如果没有重边，那么剖分数至多是 $O(\sqrt{m})$ 的。随机图就更不用说了。好像用来骗分很爽的。