M_sea的博客

M_sea的博客

A Mengbier

题解 CF1156D 【0-1-Tree】

posted on 2019-05-04 18:13:04 | under 题解 |

讲一下楼上/下说的“复杂度 $O(n\log n)$ 但是好打也好理解很多的并查集做法” 。

考虑所有答案点对有哪几种情况:全 $0$ 、全 $1$ 、一段 $0$ 接一段 $1$ 。

只保留树上所有 $0$ 边,形成一个森林,我们把这个森林称为 $0$ 森林。

那么对于 $0$ 森林内的每个连通分量,会产生 $sz(sz-1)$ 个全 $0$ 对。

用并查集维护连通分量,这样子就处理完了所有全 $0$ 点对。

全 $1$ 点对和全 $0$ 点对是类似的。

现在考虑一段 $0$ 接一段 $1$ 怎么做。

对于一个一段 $0$ 接一段 $1$ 的点对 $(u,v)$ ,显然会存在一个点 $t$ ,使得 $(u,t)$ 全 $0$ 、 $(t,v)$ 全 $1$ 。

那么枚举 $t$ ,它的贡献就是 $(sz_0-1)(sz_1-1)$ ,这里的 $sz_0$ 指的是 $t$ 在 $0$ 森林中所属连通分量的大小, $sz_1$ 类似。

那么这题就做完了。

代码