题解：CF2135C By the Assignment

· · 题解

省流：给你一个无向联通简单图，图上某些点的点权（第 i 个点的点权记为 p_i）已被固定，剩下的点权未知，对于同一个点对 u,v，从 u 到 v 的所有路径的点权异或和都是同一个值，求未知的点权有多少填充方式（保证点权 \in[0,V)）。

显然，如果图是树，那么树上的节点可以随便填权值，因为两两之间路径唯一。
然后考虑一般图。
首先，这题是性质题。
一个一个看性质。

【性质 1】
省流：任意一个长度为 |R| 的环 R 上随便剖出一条长为 |R|-2 的链，链的异或和都是 0。

不难发现，若 u,v 之间有连边，并且其还有其他路径可互相到达的话，就会构成一个环。
由于同一个点对 u,v，从 u 到 v 的所有路径的点权异或和都是同一个值，所以说 p_u\oplus p_v 的值等于 p_u\oplus p_v 再异或上环上所有其他节点的异或和。
这就意味着环上所有其他节点的异或和是 0。
对于这个环上的任意相邻点对来说都是一样的，所以这个性质得证。

【性质 2】
省流：任意环的异或和都是 0。

相当于把性质一做了推广。
如果环 R 的异或和不是零，又因为性质一，所以这意味着每一个相邻点对的异或和都不是 0。
但是，你考虑环上两个点 u,v 之间隔了一个点 c 的情况，那么显然 p_c 等于环上 u,v,c 的补的异或和。
我们让 p_c 和环上 u,v,c 的补同时异或上 p_u，显然环上 u,v,c 的补会和 u 构成一条长为 |R|-2 的链，异或和为零。
然而 p_c\oplus p_u 根据前面的反设，不是 0，所以得到矛盾。
因此任意环的异或和都是 0。

【性质 3】
省流：任意奇环上的所有点权都是 0。

首先，根据性质 2，显然奇环上的所有点点权都相等。
所以只能全都是 0，因为是奇数个。

【性质 4】
省流：任意偶环上的所有点权都相等。

这个反证一下也是挺显然的。

【3，4 推论】

  1. 如果某个奇环和偶环有交，那么两个环的并上的所有点都是 0。
  2. 如果某个偶环和偶环有交，那么两个环的并上的所有点权都相等。

有了这几个性质，答案呼之欲出。
就是对原图跑 Tarjan 求出每一个边双连通分量。
为啥，因为边双连通分量本质上就是一堆环的并。
对于每一个边双联通分量，如果不是二分图，那么这个边双上所有点都是 0。
如果是二分图，那么这个边双上所有点权都相等。
判二分图就是找奇环，BFS 黑白染色即可。

最后，关于已经钦定点权的点，那个其所在的整个边双的点权都与它相等。（除非它不是 0 但是其所在边双有奇环，此时原图不合法，填充方案数为 0）
没有钦定的就乘法原理即可。
所以最终答案是 V 的没被钦定的二分图边双个数次方。（好绕）