题解：CF231E Cactus

KidA · 2024-11-16 14:12:30 · 题解

在无向图中，对于每一个简单环，

都会产生两种不同的走法，即走环的「上侧」或「下侧」。（可自行画图理解）

因为本题保证了是点仙人掌，于是设两点间的路径上有 n 个环，则答案即为 2^n。

不难想到缩点形成一棵树，这样就可以简单地使用树上差分统计贡献了。

时间复杂度是 O(q \log n) 的。实现。

感觉思路和代码都十分自然。最多上位绿。