路径考虑顺序。
显然合法的路径只有以下两种:
- 一段 \(0\) 加一段 \(1\) 或一段 \(1\) 加一段 \(0\)。
- 全 \(0\) 或全 \(1\)。
用并查集将边权为 \(0\) 和 \(1\) 的边分别缩起来,对于一个大小为 \(siz\) 的连通块,第二种的答案是 \(siz(siz-1)\)。
对于第一种,我们枚举 \(0\) 和 \(1\) 的分界点,它所在 \(0\) 和 \(1\) 的连通块的大小分别是 \(siz_0\) 和 \(siz_1\),它的答案便是 \((siz_0-1)(siz_1-1)\)。
然后这题就做完了,统计连通块大小的时候还能顺便按秩合并。