【AtCoder Grand Contest 035 C】Skolem XOR Tree | Mrsrz's blog

构造

题目大意：

给定 $n$，要求构造 $2n$ 个结点的树，满足：

• 对于 $1\leq i\leq n$，结点 $i$ 和 $i+n$ 的权值为 $i$。
• 对于 $1\leq i\leq n$，结点 $i$ 到 $i+n$ 的简单路径上的所有点权的异或和为 $i$。

若没有可行方案则输出 No，否则给出方案。

题解：

当 $n=2^k$ 时，无解。因为二进制第 $k$ 位为 $1$ 的只有 $n$ 和 $2n$ 两个结点，这两个结点异或后为 $0$，中间的结点无论如何都无法得到最高位的 $1$。

考虑 $2n$ 和 $2n+1$ 的异或和为 $1$，所以构造这样的一条链 $(2n)-(2n+1)-1-(2n)-(2n+1)$ 满足条件。

由于是一棵树，我们可以取出一个 $1$ 共用。另外一个 $1$ 随便接到一条链尾部即可。

然后对于 $n$ 为奇数的情况就构造完毕了。

我们发现此时共用的 $1$ 旁边恰好有 $2\sim n$。这些结点，然后对于 $n$ 为偶数的情况，我们要找到 $2\sim n$ 中两个不同的数，其异或和为 $1$。显然存在解。

于是构造完毕。

Code：

#include<cstdio>
int n;
int main(){
    scanf("%d",&n);
    if(n==1<<(31-__builtin_clz(n)))return puts("No"),0;
    puts("Yes");
    printf("%d %d\n%d 3\n3 1\n1 2\n2 %d\n",1+n,2+n,2+n,3+n);
    for(int i=4;i+1<=n;i+=2)
    printf("%d %d\n%d 1\n1 %d\n%d %d\n",i+n,i+1,i+1,i,i,i+1+n);
    if(n%2==0){
        int x=__builtin_ctz(n);
        printf("%d %d\n%d %d\n",n,1<<x,n^1^(1<<x),2*n);
    }
    return 0;
}