题目链接
https://codeforces.com/contest/1907/problem/G
题目大意
给定一个长度为 \(n\) 的 \(01\) 串，有 \(n\) 个开关，按下第 \(i\) 个开关会反转位置 \(i\) 和位置 \(a_i\) 的状态（\(a_i \neq i\)），目标是让 \(01\) 串的状态变为全 \(0\) 。
报告无解，若有解，输出操作次数最少的方案。
数据范围
多组测试数据，保证
- \(\sum n \le 2\times 10^{5}\)
- \(1 \le a_i \le n, a_i \neq i\)
解题思路
注意到每个开关控制且仅控制两个位置的状态，所以我们可以把开关抽象成边，把每个位置抽象成一个结点。
我们发现总共有 \(n\) 个节点 \(n\) 条边，但是图不保证联通，所以建完图之后是一个基环树森林。
问题变为给定一个基环树森林，选择最小的边集，使得反转边集中所有边连接的两个结点的状态后，所有结点的状态都变为 \(0\) 。
其实只需要考虑一个基环树上怎么做。
首先可以注意到这颗基环树上状态为 \(1\) 的结点个数必须为偶数个，否则肯定无解。
其次可以注意到一条边只会被选择 \(0\) 次或者 \(1\) 次，选择 \(2\) 次跟 \(0\) 次的结果相同，所以我们可以将基环树上的环断掉，比一下选断掉的边和不选断掉的边哪个更优即可。
于是只需要考虑在一颗树上怎么做。
先假设只有两个状态为 \(1\) 的结点，显然最小的边集一定是两点简单路径上所有的边。
假设有四个呢？如果我们随便两两配对，发现路径可能有交集，这样是不优的，但是我们发现只要把路径交集去掉不选，剩下的不交的部分又构成两条新的路径，这样一定是最优的。
所以到此为止此题基本结束，我们只需要按照任意顺序给状态为 \(1\) 的结点配对，把所有配对的点对的路径上所有边的值加 \(1\) ，最后选择值为奇数的边即为最优方案。
用树上差分加上倍增求 lca 实现的话为 \(O(n\log n)\) ，瓶颈为倍增求 lca 。