U224599 Crosswater
题目描述
一个集合的 mex+ 定义为不出现在其中的最小 **正整数**，例如 $\operatorname{mex}^{+}(\{1,2,3\})=4$，$\operatorname{mex}(\{0,1,4,9\})=2$，$\operatorname{mex}^+(\{0,1,2,3,4\})=5$ .
有一棵树，每个点 $u$ 有点权 $a_u$，$q$ 次询问，每次询问点 $u$ 到点 $v$ 简单路径上所有点点权的 mex+ .
保证 $\{a\}$ 是一个排列 .
输入格式
使用随机数生成器：
```cpp
// C++
#include
#include
#include
using namespace std;
const int N = 12345;
int n, q, a[N], fa[N];
class __gen
{
public:
typedef uint32_t u32;
typedef uint64_t u64;
explicit __gen(const u32& seed)
{
z0 = z1 = seed;
z2 = (~seed) ^ 233114514u;
z3 = seed ^ 233191981u;
z4 = (~(z1 + z2 - z3) | 1) + 1;
x = seed - 1;
}
u32 operator()()
{
z1 = splitmix64(z1 + z0) ^ x;
z2 = splitmix64(z2 + z1) ^ x;
z3 = splitmix64(z3 + z2) ^ x;
z4 = splitmix64(z4 + z3) ^ x;
return z1 ^ z2 ^ z3 ^ z4;
}
private:
unsigned z0, z1, z2, z3, z4, x;
inline u64 splitmix64(const u64& v) const
{
u64 z = (v + 0x9e3779b97f4a7c15);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
return z ^ (z >> 31);
}
};
int main()
{
unsigned seed;
scanf("%d%d%u", &n, &q, &seed);
__gen rnd(seed); a[1] = 1;
for (int i=2; i
输出格式
输出所有答案的异或和即可 .
说明/提示
样例 1 解释：
异或前的询问答案分别是 2, 1, 4，异或和为 7 .
***
数据范围：
对于 $20\%$ 的数据，$n\le 10^3$，$q\le 10^2$ .
对于 $50\%$ 的数据，$n\le 100$，$q\le 10^5$ .
对于全部数据，有 $1\le n\le 10^4$，$1\le q\le10^5$，$seed$ 在 32 位无符号整型表示的范围内 .