[AGC004F] Namori
题意
给一棵 \(n\) 个点的树或基环树。每个点初始都是白色的。每次可以选一条端点颜色相同的边 \((u, v)\)，并反转 \(u\) 和 \(v\) 的颜色。询问能否将每个点都变为黑色，若能，输出最小操作数；否则输出 \(-1\)。
\(n \leq 10^5\)。
题解
树
考虑对树黑白染色来刻画操作，那么问题即：
- 一开始有一些黑点和白点，通过交换相邻的黑点和白点使得最终每个点的颜色改变。
对每条边算贡献即可。\(u\) 的连父边被操作的次数是 \(u\) 子树内黑点与白点个数之差。
偶环基环树
设某一条环上的边为 \((u, v)\)，我们删去这条边，图会变成一棵树，我们可以先求出 \(w(u) = \sum_{v \in \text{sub}(u)} [v \text{ is black}] - [v \text{ is white}]\)，若不考虑这条边，\(ans = \sum \left|w(i)\right|\)。
WLOG 我们设固定根后浅的点为 \(u\)。假设 \((u, v)\) 被操作了 \(x\) 次，那么相当于 \(u \leadsto root\) 的点 \(w(i) \gets w(i) + x\)，\(v \leadsto root\) 的点 \(w(i) \gets w(i) - x\)。
此时答案为 \(ans = \sum_{i \notin \text{cycle}} |w(i)| + \sum_{i\in (u\leadsto root)} \left|-w(i)-x\right| + \sum_{i \in (v \leadsto root)} \left|w(i)-x\right| + |0 - x|\)。
第一个和式显然为常数，后面的部分让 \(x\) 取中位数即可最优。
奇环基环树
我们仍然拿出任意一条环上的边 \((u, v)\) 来特殊处理。此时操作一次 \((u, v)\) 的效果是把这两个点的颜色取反。
那么显然交换颜色的操作和这条边是没关系的。上述两种情况有解当且仅当 \(w(root) = 0\)，此时这条边的作用是当 \(w(root) \ne 0\) 但 \(2 \mid w(root)\) 时将其归零，交换操作的最优策略仍然和树是一样的。