xhr 的奇思妙想

恩，大概是这么个问题：

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

于是想了一下没有结果，打个程序试试，发现随机图上差不多就是 \(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})\) 的。随机图就更不用说了。好像用来骗分很爽的。