新高一暑假第一期集训恢复性训练【数据结构-并查集】（补）

新高一暑假第一期集训恢复性训练【数据结构-并查集】（补）

C. [POJ1417] True Liars

先将题目中的好人和坏人转换一下，也即是如果 \(x\) 说 \(y\) 是好人，则他们两属于同一组，反之则不属于同一组。

然后我们可以想到带权的并查集，用 \(val_x\) 代表 \(x\) 与其父节点的关系，当 \(val_x\) 为 \(0\) 时 \(x\) 与其父亲同类，为 \(1\) 时不同类。由于这是一个传递的关系，所以会 \(\mod 2\)。

假定我们已经分好了类，那么就会有 \(n\) 个集合，每个集合有与父节点同类的，也有不同类的。

如果我们现在要确定出好人的数量，那么在每个集合里面只能选一种，这时就用 dp 来处理：设 \(f_{i, j}\) 的含义是处理到第 \(i\) 个集合时，和为 \(j\) 的方案总数。

那么初始化 \(f_{0, 0} = 1\)，转移方程为 \(f_{i, j} = f_{i, j} + f_{i - 1, j - t_0/j - t_1}\)，\(t_0\)，\(t_1\) 为 \(i\) 集合中的两类的数量。

最后注意，如果 \(p1\) 等于 \(0\)，也会输出一个 end。