「AtCoder AGC035-C」Skolem XOR Tree

Description

构造一棵 $2n$ 个点的树，点的编号为 $1 \sim 2n$，其中编号为 $i$ 和 $n + i$ 的点的权值为 $i\ (1 \leq i \leq n)$，使得 $i$ 到 $n + i$ 的路径上所有点的点权异或和为 $i$（包括 $i$ 和 $n + i$ 本身）。

$(1 \leq n \leq 10^5)$

Source

[AtCoder]AGC035-C

Solution

考虑转化问题，对于编号为 $i$ 和 $n + i$ 的点，设它们路径上除自己外所有点的异或和为 $sum$，则有 $i \oplus sum \oplus i = i$，化简可得 $sum = i$ 。所以我们必须要找到若干个点，满足点权异或和为 $i$ 。

首先当 $n$ 是 $2$ 的幂时无解（包含 $n = 1$），因为此时不存在任何其它点的异或和为 $n$（$n$ 二进制下最高位的 $1$ 肯定无法得到）。

一种可行的构造方法是：

把节点 $1$ 当做根。我们可以把 $x$ 和 $x \oplus 1$ 与根连接（如图）。

这样恰好可以同时使 $x$ 和 $x \oplus 1$ 符合条件，而且不需要其它权值的节点。当 $x$ 是偶数时，$x \oplus 1 = x + 1$，所以我们可以把除根节点之外的点分成若干组：$\{2,3\},\{4,5\},\{6,7\},\cdots$，每一组都用上述方法构造。至于最后多出来的节点 $n + 1$，因为 $x \oplus (x \oplus 1) = 1$，所以可以接在第三层中任意一个节点的下面，为了方便这里把 $n + 1$ 接在了 $3$ 的下面。

下图是一个例子（$n = 7$）：

注意这样做当 $n$ 为偶数时会多出 $2$ 个节点 $n$ 和 $n + n$ 。考虑怎么在已构造的树上放置这 $2$ 个节点。

此时我们可以找到 $n$ 在二进制下最高位上的 $1$ 在第 $bit$ 位，然后把 $n$ 接在权值为 $2^{bit} \oplus 1$ 的点下面（由于 $2^{bit}$ 一定是偶数，所以等价于 $2^{bit} + 1$）。很容易证明这个值是大于 $1$ 且小于 $n$ 的，且一定能在树的第二层找到权值为这个值的点（这个值是奇数，所以点的编号应为 $(2^{bit} \oplus 1) + n$）。$n$ 到根的异或和（不含自己）为 $2^{bit} \oplus 1 \oplus 1 = 2^{bit}$，我们只需要把 $n + n$ 接在 $n \oplus 2^{bit}$ 的下方，就能符合题目的条件（因为 $2^{bit} \oplus (n \oplus 2^{bit}) = n$，且能够保证 $n \oplus 2^{bit} < n$，还是一个偶数，同样可以在第二层找到权值为这个值的点）。

下图是一个例子（$n = 6$）：

Remarks

Special Judge 写法：假设 $1$ 号节点为根，预处理出所有节点到根的路径异或和，枚举权值 $i$，用树上差分求路径异或和。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int n, m, bit;

inline void printEdge(int u, int v) {//输出无向边 u -> v
    write(u);
    putchar(' ');
    write(v);
    putchar('\n');
}

int main() {
    read(n);
    for (int i = 0; (1 << i) <= n; ++i)
        if (n == (1 << i)) {//判断是否为 2 的幂 
            puts("No");
            return 0;
        }
    puts("Yes");
    for (int i = 2; i + 1 <= n; i += 2) {
        printEdge(1, i), printEdge(i, i + 1);
        printEdge(1, i + n + 1), printEdge(i + n + 1, i + n);
        //对于每组 { x, x ^ 1 } 连边 
    }
    printEdge(3, n + 1);//把 n + 1 接在 3 的下面 
    if (!(n & 1)) {// n 是偶数 
        for (int i = 0; (1 << i) <= n; ++i)
            if (n & (1 << i)) bit = i;//找到最高位的 1 
        printEdge(((1 << bit) ^ 1) + n, n), printEdge(n ^ (1 << bit), n << 1); 
    }
    return 0;
}