题目标签
- B
- 笛卡尔树的应用
- C
- 有思维难度的 dp / 递推
- D
- 交互题
- 利用曼哈顿距离反过来解坐标：二元线性方程组
- 考虑“问最值/极限情况”
- E
- 二分图，边双连通分量
- 两条路径 -> 环
- 异或运算的性质
- （见题解）
题解：E. By the Assignment
- 观察1：对于本题，每个边双连通分量内部的点权可以独立决定
- 观察2：对于一个环，环上的点权两两相等
- 对于点 \(v_1, v_2, \cdots v_l\) 构成的环，考虑 \(v_i, v_j( i\neq j)\) 之间的路径，则有 \(\bigoplus_{k \neq i, j} v_k = 0\)
- 考虑 \(i, j_1, j_2\) 则有 \(0 = \left(\bigoplus_{k \neq i, j_1} v_k\right) \oplus \left(\bigoplus_{k \neq i, j_2} v_k\right) = v_{j_1} \oplus v_{j_2}\)
- 于是得到 \(v_{j_1} = v_{j_2}\)，进而环上所有点权都必须相等
- 观察3：在观察2 的基础上，如果环为奇环，则所有点权都必须为 0
基于以上观察，我们设计出如下算法：
- 单独处理每一个边双连通分量
- 统计边双内是否存在奇环，若存在，直接检查是否能所有点涂成 0；若不存在奇环，则检查是否能将所有点涂成同一颜色、以及方案数
容易验证这样涂色之后的图是符合题目要求的
My Submission